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.

Answer 2

The answer provided by @Dhruv is a good one. In addition to that here is one another solution that works in O(n) time.
We need to keep track of the previous node in this approach. In each recursive call we check the previous node data with the current node data. If current node data is less than previous we return false

int isBST(node* root) {
  static node* prev  = NULL;

  if(root==NULL)
    return 1;

  if(!isBST(root->left))
    return 0;

  if(prev!=NULL && root->data<=prev->data)
    return 0;

  prev = root;
  return isBST(root->right);
}

Answer 3

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max){
  if(node == null){
    return true;
  }

  boolean left  = isBinarySearchTree(node.getLeft(), min, node.getValue());
  boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

  return left && right && (node.getValue()<max) && (node.getValue()>=min);      
}

Comments are invited. Thanks.

Answer 4

I think that the second approach is right. The tree can be traversed in a recursive manner. On each iteration lower and upper bounds of current subtree can be stored. If we want to check subtree with root x, and bounds for the subtree are l and h, then all we need is to check that l <= x <= h and to check the left subtree with bounds l and x, and the right one with bounds x and h.

This will have O(n) complexity, because we start from the root and each node is checked only once as root of some subtree. Also, we need O(h) memory for recursive calls, where h is the height of the tree.

Answer 5

There are some examples above using INTEGER.MAX AND MIN I cant see a reason to pass them and the significance of it, correct me if I am wrong in anyway or explain me the reason.

More over binary search tree may have objects which are compared by compareTo method or Coperator.. ( hence Integer.MIN and Integer.MAX dont fit on that model) I am writing a code where it returns true or false one has to call (root_node,true) and it will return true if it is a bst else false

void boolean isBSt( node root_node, boolean passed_root)
{

  if ( node==null){
        if ( passed_root)
        return false;
        // you have passed null pointer as 
        //root of the tree , since there is no 
        // valid start point we can throw an exception or return false      
        return true;
   }

  if( node.right !=null ) 
     if ( node.right.data <= node.data)
   return false;

  if ( node.left !=null ) 
        if ! ( node.left.data <= node.data) 
    return false;

  return ( isBST( node.right , false) && isBST( node.left, false ) )

}

Answer 6

Have a look at this solution: http://preparefortechinterview.blogspot.com/2013/09/am-i-bst.html

It explains different ways and gives you a generic and efficient method too. Hope it helps.

Answer 7

Here is another Solution which uses 2 helper functions to calculate for each node the min and max value in the subtree using the helper function minValue and maxValue

int isBST(struct node* node)
    {
      if (node == NULL)
        return(true); 

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

      /* false if the min of the right is <= than us */
        if (node->right!=NULL && minValue(node->right) < node->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);
    }