Programming Interview Questions 7: Binary Search Tree Check

This is a very common interview question. Given a binary tree, check whether it’s a binary search tree or not. Simple as that..

The first solution that comes to mind is, at every node check whether its value is larger than or equal to its left child and smaller than or equal to its right child (assuming equals can appear at either left or right). However, this approach is erroneous because it doesn’t check whether a node violates any condition with its grandparent or any of its ancestors. The following tree would be incorrectly classified as a binary search tree, the algorithm won’t be able to detect the inconsistency between 3 and 4:

So, we should keep track of the minimum and maximum values a node can take. And at each node we will check whether its value is between the min and max values it’s allowed to take. The root can take any value between negative infinity and positive infinity. At any node, its left child should be smaller than or equal than its own value, and similarly the right child should be larger than or equal to. So during recursion, we send the current value as the new max to our left child and send the min as it is without changing. And to the right child, we send the current value as the new min and send the max without changing. This approach leads to the following code:

```class Node: def __init__(self, val=None): self.left, self.right, self.val = None, None, val   INFINITY = float("infinity") NEG_INFINITY = float("-infinity")   def isBST(tree, minVal=NEG_INFINITY, maxVal=INFINITY): if tree is None: return True   if not minVal <= tree.val <= maxVal: return False   return isBST(tree.left, minVal, tree.val) and \ isBST(tree.right, tree.val, maxVal)```

There’s an equally good alternative solution. If a tree is a binary search tree, then traversing the tree inorder should lead to sorted order of the values in the tree. So, we can perform an inorder traversal and check whether the node values are sorted or not. Here is the code:

```def isBST2(tree, lastNode=[NEG_INFINITY]): if tree is None: return True   if not isBST2(tree.left, lastNode): return False   if tree.val < lastNode[0]: return False   lastNode[0]=tree.val   return isBST2(tree.right, lastNode)```

I personally like this question a lot because it’s simple (but not trivial) and demonstrates the basic knowledge of binary search trees and tree traversals.

VN:F [1.9.22_1171]
Programming Interview Questions 7: Binary Search Tree Check, 8.9 out of 10 based on 56 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
• Igor Yagolnitser

Hey Arden,

Didn’t know you had this blog, but that’s a great idea!
I’d like to contribute to it when I get some time.
As for the in order traversal above: where are you adding to the node list?
A special note about these types of problems when interviewing at Microsoft: while algorithmically your solution should be recursive, your implementation should be prefixed by: “the problem with the recursive implementation is that it’s only good when you know the depth, otherwise you can easily blow the stack”. This shows you understand the practical difference between writing code in a classroom and in a production environment. If the interviewer then says: “let’s say you don’t need to worry about that”, you proceed with your solution, but twice in my own experience the problem was precisely about whether I would just rush to implement the obvious and well known book solution, or stop to consider the real world implications.
Just a thought.
Good luck.

• Arden

Hi Igor, thanks for the comment. You’re right about recursion and stack space. I didn’t mention that because both of the algorithms are recursive. If we would like to code it iteratively, than we have to maintain a queue, which will use the heap space. But as you said, it’s definitely useful to first step back and thoroughly analyze all the possible solutions with their real world implications, and then start coding the actual algorithm.

• Oren

@Igor Well, with respect to the stack, isBST is preferable to isBST as it’s tail recursive.

@Arden these posts have been a life saver! Great writing coupled with a diverse and interesting collection of problems. Thanks!

• Anonymous

There’s no reason to build a list of all node values in isBST2. You only need the value of the last node visited so far. Rename nodes to maxValBox and update it like this:

maxValBox[0] = tree.val

• Arden

You’re right, changed it. Thanks for the comment..

• Shubham

Why don’t you just get the inorder and if that’s really “in order” you are done.

• harsh sharma

its almost the same problem if you have to find successor of x and x.right=NULL,in that case we have to find the first parent whose child is left child to him.and same in case of predecessor if x.left =NULL.

• Anonymous

I’m preparing for interviews, your questions and explanations are very helpful! Thank you very much!

• Abhishek Srinath

/*
Returns true if a binary tree is a binary search tree.
*/
int isBST(struct node* node) {
if (node==NULL) return(true);

// false if the min of the left is > than us
if (node->left!=NULL && minValue(node->left) > node->data && node->left->data > node->data)
return(false);

// false if the max of the right is right!=NULL && maxValue(node->right) data && node->right->data data)
return(false);

// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);

// passing all that, it’s a BST
return(true);
}

• Fatih

Here is the C# version:

public Boolean validate()

{

if (root.LeftNode.Value >= root.Value || root.RightNode.Value root.Value || (minimum!=-1 && leftNodeValue <= minimum))

{

return false;

}

}

if (rightNode != null)

{

int rightNodeValue = rightNode.Value;

if (rightNodeValue = maximum))

{

return false;

}

}

Boolean rightNodeResult = isValid(root.RightNode, root.Value, maximum);

Boolean leftNodeResult = isValid(root.LeftNode, minimum, root.Value);

return ( rightNodeResult&&leftNodeResult );

}

• Benji

This statement is incorrect: “The following tree would be incorrectly classified as a binary search tree”

The image you have is BST, it’s just not a [b]balanced[/b] BST.

• Gary Tse

Could you just check whether the max and min depth differ by no more than 1, as the solution in Cracking the Coding Interview states?

• Sat

Can a BST have duplicates ? If so, will the inorder solution work – Take the case of a complete binary tree with 3 nodes, all having the same value, say 4. This is not a BST. With the inorder approach we might conclude calling it a BST.

• Abhishek Tamhane

I guess we will have to make sure the inorder traversal is strictly increasing to handle that case.

• Stephen

In “isBST2”, I don’t think you need to pass “lastNode” as an argument to any of the recursive calls. You never change the lastNode from the list object created in the defaults, you just keep changing the contents of that list.