Engaged Employer

Interview Question

IOS Developer Interview Menlo Park, CA

Verify that a binary search tree is indeed a binary search

tree.

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
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 <= 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
0

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

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

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

Ker on Feb 26, 2015