## Interview Question

## Interview Answer

4 Answers

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);

}

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

}

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

//

## Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up

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 }));

}

RahulonMay 2, 2013