Determine if given Binary Tree is a BST or not

Given a Binary Tree, determine if it is a BST or not.

 

This problem has a simple recursive solution. The BST property “every node on the right subtree has to be larger than the current node and every node on the left subtree has to be smaller than the current node” is the key to figuring out whether a tree is a BST or not.
 

The greedy algorithm – simply traverse the tree, at every node check whether the node contains a value larger than the value at the left child and smaller than the value on the right child – does not work for all cases. Consider the following tree:

     20
    /  \
  10    30
       /  \
      5    40

In the tree above, each node meets the condition that the node contains a value larger than its left child and smaller than its right child hold, and yet it is not a BST: the value 5 is on the right subtree of the node containing 20, a violation of the BST property.

Instead of making a decision based solely on the values of a node and its children, we also need information flowing down from the parent as well. In the case of the tree above, if we could remember about the node containing the value 20, we would see that the node with value 5 is violating the BST property contract.

So the condition we need to check at each node is:

  • if the node is the left child of its parent, then it must be smaller than (or equal to) the parent and it must pass down the value from its parent to its right subtree to make sure none of the nodes in that subtree is greater than the parent
  • if the node is the right child of its parent, then it must be larger than the parent and it must pass down the value from its parent to its left subtree to make sure none of the nodes in that subtree is lesser than the parent.

C++ implementation –
 

Download   Run Code

Output:

This is NOT a BST!

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

Another approach:
 

We know that an in-order traversal of a binary search tree returns the nodes in sorted order. Thus, to determine if given binary tree is BST or not, we can perform in-order traversal and keep track of the last visited node while traversing the tree and check whether its key is smaller (or smaller/equal, if duplicates are to be allowed in the tree) compared to the current key.

 
C++ implementation –
 

Download   Run Code

Output:

This is NOT a BST!

 
The time complexity of above solution is O(n).
 

References:
https://en.wikipedia.org/wiki/Binary_search_tree

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz