Largest BST Subtree LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg ByteDance Facebook MicrosoftViews 2230

Problem Statement

The Largest BST Subtree LeetCode Solution problem says given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree having the largest number of nodes.

Note: A subtree must include all of its descendants.

In a Binary Search Tree (BST), the left subtree values are less than the value of their parent node’s value and the right subtree values are greater than the value of their parent node’s value.

Example:

Test Case 1:

Input:

root = [10, 8, 15, 1, 5, 7, 30, null, null, null, null, null, null, 17, 32]

Output:

5

Explanation for Largest BST Subtree:

From the below figure we can easily know the largest Binary search tree present. The number of elements in that Binary search tree is 5.

Largest BST Subtree LeetCode Solution                                   Largest BST Subtree LeetCode Solution

Approach

Idea:

We know a tree is a valid Binary search tree if its left and right subtrees are Binary search trees. So we can follow a bottom-up approach. While moving from 1 node to its parent, we can pass some information that will help us determine if the rules of the Binary search tree hold true for the parent node or not.

If the subtrees are Binary search trees, then the tree from the parent node is a Binary search tree if the parent node’s value is more than the maximum value in the left sub-tree and if the parent node’s value is less than the minimum value in the right sub-tree. So we can pass this information while moving from 1 node to its parent node. We can also pass the max BST size so far.

So we can understand that before processing a node, we need values of its child nodes. We know in Post-Order traversal, the child nodes are processed before the parent node. So we can find out that we need to apply Post-Order traversal here.

So from every node, we will pass these values to its parent node.

i) min node value in the subtree.

ii) max node value in the subtree

iii) max size of the BST in the subtree

Code

Java Program for Largest BST Subtree LeetCode Solution

class TreeNodeValue {
  public int maxValue, minValue, maxSize;
  TreeNodeValue(int maxValue, int minValue, int maxSize) {
    this.maxValue = maxValue;
    this.minValue = minValue;
    this.maxSize = maxSize;
  }
}
class Solution {
    public TreeNodeValue largestBSTSubtreeHelper(TreeNode root) {
      // System.out.println("Root "+root);
      if(root==null) {
        return new TreeNodeValue(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
      }
      
      TreeNodeValue leftSubtree = largestBSTSubtreeHelper(root.left);
      // System.out.println("Left"+" "+leftSubtree.minValue+" "+leftSubtree.maxValue+" "+leftSubtree.maxSize);
      TreeNodeValue rightSubtree = largestBSTSubtreeHelper(root.right);
      // System.out.println("Right"+" "+rightSubtree.minValue+" "+rightSubtree.maxValue+" "+rightSubtree.maxSize);
      
      if(leftSubtree.maxValue < root.val && rightSubtree.minValue > root.val) {
         return new TreeNodeValue(Math.max(root.val,rightSubtree.maxValue), Math.min(root.val,leftSubtree.minValue), leftSubtree.maxSize+rightSubtree.maxSize+1);
      }
      
      return new TreeNodeValue(Integer.MAX_VALUE, Integer.MIN_VALUE, Math.max(leftSubtree.maxSize,rightSubtree.maxSize));
    }
    public int largestBSTSubtree(TreeNode root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
}

C++ Program for Largest BST Subtree LeetCode Solution

class TreeNodeValue {
public:
    int maxValue, minValue, maxSize;
    
    TreeNodeValue(int maxValue, int minValue, int maxSize) {
        this->maxValue = maxValue;
        this->minValue = minValue;
        this->maxSize = maxSize;
    }
};

class Solution {
public:
    TreeNodeValue largestBSTSubtreeHelper(TreeNode* root) {
        if (!root) {
            return TreeNodeValue(INT_MIN, INT_MAX, 0);
        }
        
        auto leftSubtree = largestBSTSubtreeHelper(root->left);
        auto rightSubtree = largestBSTSubtreeHelper(root->right);
        
      
        if (leftSubtree.maxValue < root->val && root->val < rightSubtree.minValue) {
            return TreeNodeValue(max(root->val, rightSubtree.maxValue), min(root->val, leftSubtree.minValue), 
                            leftSubtree.maxSize + rightSubtree.maxSize + 1);
        }
        
        return TreeNodeValue(INT_MAX, INT_MIN, max(leftSubtree.maxSize, rightSubtree.maxSize));
    }
    
    int largestBSTSubtree(TreeNode* root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
};

Complexity Analysis for Largest BST Subtree LeetCode Solution

Time Complexity

Here we are visiting each node only once. So the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity

The recursion stack takes O(H) space, where H is the height of the tree. In the worst case, H = n. So the space complexity is O(n).

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

https://en.wiktionary.org/wiki/subtree

 

 

 

 

 

 

 

Translate »