Facebook Interview Question: Verify that a binary search t... | Glassdoor

Interview Question

IOS Developer Interview Menlo Park, CA

Verify that a binary search tree is indeed a binary search

  tree.
Answer

Interview Answer

10 Answers

1

public static boolean isBST(Node n)
{
    if (null == n) return true;
    return (null != isBSTI(n));
}

public static ArrayList isBSTI(Node n)
{
    int min = n.val;
    int max = n.val;
    if (left != null)
    {
        ArrayList leftR = isBST(n.left);
        if (leftR.get(1) > val) return null;
        min = leftR.get(0);
    }
    if (right != null)
    {
        ArrayList rightR = isBST(n.right);
        if (rightR.get(0) (Arrays.asList(new Integer[] { min, max }));
}

Rahul on May 2, 2013
4

The idea is if we traverse binary search tree "in-order", output of number is in ascending orders.
So here it goes. Not checked for syntax errors, but should work.

BOOL Inorder(NODE *node)
{
    static NODE *prev = NULL; // Do need to initialize this as statics are zeroed memory.

    if (node == NULL) {
        return true;
    }
    if (false == Inorder(node->left)) {
        return false;
    }
    if (prev && node->num num) {
        return false;
    }
    prev = node;
    return Inorder(node->right);
}

Friend on May 9, 2013
1

Principle. Every node in a binary tree must have left node value parent node

Bool checknode(node)
{
   If node.left then
   {
      If node.left.value > node.value then
          Return false
      If checknode(node.left) == false then
          Return false
   }
   If node.right then
   {
      If node.right.value < node.value then
          Return false
      If checknode(node.right) == false then
          Return false
   }
   Return true
}

Gus on Aug 11, 2013
0

Very simple and efficient way:

public static boolean isBinaryTree(TreeNode root) {
        if(root == null) return true;

        if(!((root.rightSon == null || root.value root.leftSon.value)))
            return false;

        if(!(root.rightSon == null || isBinaryTree(root.rightSon)))
            return false;

        if(!(root.leftSon == null || isBinaryTree(root.leftSon)))
            return false;

        return true;
    }

This is the class TreeNode in java:

class TreeNode
{
    public int value;
    public TreeNode rightSon;
    public TreeNode leftSon;

    public TreeNode(int value, TreeNode rightSon, TreeNode leftSon) {
        this.value = value;
        this.rightSon = rightSon;
        this.leftSon = leftSon;
    }
};

you can try with this example:

        //Decide if is a binary tree
        TreeNode tree = new TreeNode(15,new TreeNode(18,new TreeNode(22,new TreeNode(30,null,null),new TreeNode(21,null,null)),new TreeNode(16,null,null)),
                                     new TreeNode(10,new TreeNode(12,new TreeNode(13,null,null),new TreeNode(11,null,null)),new TreeNode(8,null,null)));
        boolean res = isBinaryTree(tree);

        System.out.println("Result: " + res);

//EXAMPLE:
// 15
// 10 18
// 8 12 16 22
// 11 13 21 30
//

Matteo Gobbi on Oct 24, 2013
0

private static boolean isReallyBST(Node root) {
        return followsBST(root.left, root.value, true)
                && followsBST(root.right, root.value, false);
    }

    private static boolean followsBST(Node node, Integer parent,
            boolean isLeft) {
        if (node == null) {
            return true;
        }

        boolean follows = isLeft ? node.value = parent;
        return follows && followsBST(node.left, node.value, true)
                && followsBST(node.right, node.value, false);
    }

Ker on Feb 26, 2015
1

A simpler approach is to do an inorder traversal keeping track of last seen element. If it is always increasing then we can prove that tree is BST.

Ashish Kaila on Oct 7, 2015
1

class TreeNode {
  var value: Int?
  var leftChild: TreeNode?
  var rightChild: TreeNode?
}

func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
  print("value: " + String(node.value!))
  print("min: " + String(min))
  print("max: " + String(max))

  if node.value! max
  {
      return false
  }

  if let leftChild = node.leftChild {
     if isBST(leftChild, min: min, max: node.value!) == false {
       return false
     }
  }

  if let rightChild = node.rightChild {
     if isBST(rightChild, min: node.value!, max: max) == false {
       return false
     }
  }

  return true
}

// Creating BST
let minValue = Int.min
let maxValue = Int.max

let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil

let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil

let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil

let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil

let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7

let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15

let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13

if isBST(node10, min: minValue, max: maxValue) == true {
  print("Tree is BST.")
}else {
   print("Tree is not BST.")
}

Anonymous on Mar 31, 2016
0

class TreeNode {
  var value: Int?
  var leftChild: TreeNode?
  var rightChild: TreeNode?
}

func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
  print("value: " + String(node.value!))
  print("min: " + String(min))
  print("max: " + String(max))

  if node.value! max
  {
      return false
  }

  if let leftChild = node.leftChild {
     if isBST(leftChild, min: min, max: node.value!) == false {
       return false
     }
  }

  if let rightChild = node.rightChild {
     if isBST(rightChild, min: node.value!, max: max) == false {
       return false
     }
  }

  return true
}

// Creating BST
let minValue = Int.min
let maxValue = Int.max

let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil

let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil

let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil

let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil

let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7

let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15

let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13

if isBST(node10, min: minValue, max: maxValue) == true {
  print("Tree is BST.")
}else {
   print("Tree is not BST.")
}

@Testing on Mar 31, 2016
0

boolean isBST(Node root)
{
    if (root == null) return true;
    if ((root.left != null && root.data root.right.data)) {
        return false;
    }
    return isBST(root.left) && isBST(root.right);
}

cb on Apr 24, 2016
0

Almost all the answers above, validate that each node is a valid tree, though they forgot that we might be supposed to validate the entire hierarchy. In which case, all of these method can give false true return.
Imagine the following "invalid" tree

                              27
          14 35
10 31 19 42

While each node on its own is valid (left < parent < right), the entire tree can not be considered as valid.
In such case, it would be more appropriate to convert the tree to an array (from let to parent to right recursively)
and loop linearly on the array making sure it is really sorted.

Ahmed on Dec 8, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.