Find the largest BST subtree in a given Binary Tree

Find the largest BST subtree in a given Binary Tree

Solution:

  • Traverse tree in PostOrder
  • Create Node info (isBST, size, min, max)
Algorithm:
  1. Create a class to hold (isBST, size, min, max) properties for every node
  2. Traverse in postOrder
    1. If node is null then
      1. return null
    2. If node is leaf then,
      1. return isBST = true, size = 1, min = node.data, max = node.data
    3. left = recursively call for node.left
    4. right = recursively call for node.right
    5. if left.isBST == true and right.isBST == true and left.min < node.data < right.max then
      1. return isBST = true, size = 1+ left.size + right.size, min = left.min, max = right.max
    6. else
      1. return isBST = false, size = max (left.size , right.size), min = 0, max = 0

Video

Latest Source Code:
Github: LargestBSTInBinaryTree.java


Output:

          
              25                               
              / \               
             /   \              
            /     \             
           /       \            
          /         \           
         /           \          
        /             \         
       /               \        
       18               50               
      / \             / \       
     /   \           /   \      
    /     \         /     \     
   /       \       /       \    
   19       20       35       60       
    \     / \     / \     / \   
     \   /   \   /   \   /   \  
     15   18   25   20   40   55   70   
                  \             
                  25             
                      
Largest BST size: 8
Author: Hrishikesh Mishra