Facebook

  www.facebook.com
  www.facebook.com

Interview Question

IOS Developer Interview Menlo Park, CA

Verify that a binary search tree is indeed a binary search

  tree.
Answer

Interview Answer

4 Answers

0

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

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

Rahul on May 2, 2013
2

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 <= prev->num) {
        return false;
    }
    prev = node;
    return Inorder(node->right);
}

Friend on May 9, 2013
0

Principle. Every node in a binary tree must have left node value <= parent node and right 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.rightSon.value) && (root.leftSon == 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.