Find the size of the largest BST in a Binary Tree

Given a binary tree, find the size of the largest BST (Binary Search Tree) in it.


 

The size of the largest BST in the following binary tree is 3 formed by subtree rooted at node 15.

largest BST

 
Simple solution is to traverse the binary tree in preorder fashion and for each encountered node, we check whether the subtree rooted at the node is a BST or not. If the subtree is a BST, we calculate and return the size of the subtree rooted at the node. Otherwise, we return the maximum size BST returned by the left and right subtrees.

 

Download   Run Code

Output:

The size of the largest BST is 3

 
The time complexity of this approach is O(n2) and requires O(h) extra space for the call stack where h is the height of the tree. We can improve time complexity to O(n) by traversing the tree in bottom-up manner where an information is exchanged between the child nodes and parent node which helps in determining if subtree rooted under any node is a BST or not in O(1) time.

We know that a binary tree is a BST if following properties holds true for every tree node –

  1. Left and right subtrees of every tree node are BST.
     
  2. The value of a node should be more than the largest value in the left subtree and less than the smallest value in the right subtree.

So to determine if a subtree rooted under a node is a BST or not, the left subtree should provide information about the maximum value in it and the right subtree should provide information about the minimum value in it. Also, parent node should be notified when both left and right child are also BST.

 

Download   Run Code

Output:

The size of the largest BST is 6

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 4.33 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
naresh kumar
Guest

what about the tree
……………21
…………../….\
…………/………\
………15……….28
………/.\………../.\
……./…..\……./……\
….22…..20..25…….2
what would the largest bst?
won’t
……………21
…………../….\
…………/………\
………15……….28
………..\………../
………….\……./
………….20..25
this be largest bst???