Make delicious recipes!

Find out if the given tree is BST or not

If we just check the root, left, right property of every node, and all of them are BSTs in themselves, we cannot say the resulting tree is also BST. For example:


     5
    / \
   3   7
    \
     9

In the above, 3 < 5 < 7 (BST is complete for root and its immediate children).

Subtrees (involving node and their immediate children) at 3, 9 and 7 are all BSTs

Yet the whole tree is not BST because 9 lies in left subtree of 5


This indicates, that the test for BST should check to see that all the nodes lying left to a node should be smaller than that node and the nodes to the right of a node should all be greater than that node.


Due to the above property, every node should lie in a range defined by its closest right and left parents.

// Call the below as:
//    isBST (root, INT_MIN, INT_MAX);
int isBST(TreeNode node, int min, int max)
{
  if (node==NULL)
     return 1;
 
  if (node.data < min || node.data > max)
     return 0;
 
  return
    isBST(node.left, min, node.data-1) &&  
    isBST(node.right, node.data+1, max);  
}


Solution 2: Another solution is to traverse the tree in In-Order.

If the tree is BST, then in-order traversal should print a sorted output.

If we store previous in-order node and compare with current node, we can have check BST


bool isBST(TreeNode root)
{
    static TreeNode prev = NULL;
 
    if (root)
    {
        if (!isBST(root.left))
          return false;
 
        if (prev != NULL && root.data <= prev.data)
          return false;
        prev = root;
 
        return isBST(root.right);
    }
 
    return true;
}







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal