Finding if a Binary Tree is a Binary Search Tree

Question

Today I had an interview where I was asked to write a program which takes a Binary Tree and returns true if it is also a Binary Search Tree otherwise false.

My Approach1: Perform an in-order traversal and store the elements in O(n) time. Now scan through the array/list of elements and check if element at i^th index is greater than element at (i+1)^th index. If such a condition is encountered, return false and break out of the loop. (This takes O(n) time). At the end return true.

But this gentleman wanted me to provide an efficient solution. I tried but I was unsuccessful, because to find if it is a BST I have to check each node.

Moreover he was pointing me to think over recursion. My Approach 2: A BT is a BST if for any node N N->left is < N and N->right > N , and the in-order successor of left node of N is less than N and the in-order successor of right node of N is greater than N and the left and right subtrees are BSTs.

But this is going to be complicated and running time doesn't seem to be good. Please help if you know any optimal solution.

Answer 1

It's a pretty well-known problem with the following answer:

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
     if(node == null)
         return true;
     return node.value > l 
         && node.value < h
         && isValidBST(node.left, l, node.value)
         && isValidBST(node.right, node.value, h);
}

The recursive call makes sure that subtree nodes are within the range of its ancestors, which is important. The running time complexity will be O(n) since every node is examined once.

The other solution would be to do an inorder traversal and check if the sequence is sorted, especially since you already know that a binary tree is provided as an input.