Largest BST Subtree

XXX. Largest BST Subtree

Tree

Recursion

Bottom-up

Problem Statement:

Find the size of the largest subtree that is a Binary Search Tree (BST) in a binary tree.

• BST follows left < node < right property
• Count number of nodes in largest valid BST subtree
• Root of subtree must maintain BST property

Implementation:

Java Solution:

class Solution {
    // Each array holds: [min_value, max_value, largest_bst_size]
    public int largestBSTSubtree(TreeNode root) {
        int[] result = largestBST(root);
        return result[2];                          // Return size component
    }
    
    private int[] largestBST(TreeNode node) {
        // Base case: null represents valid BST
        if (node == null) 
            return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        
        // Get left and right subtree info
        int[] left = largestBST(node.left);
        int[] right = largestBST(node.right);
        
        // Check if current node forms valid BST with subtrees
        if (node.val > left[1] && node.val < right[0])
            // Valid BST: min = min(node, left_min), max = max(node, right_max)
            return new int[]{
                Math.min(node.val, left[0]),
                Math.max(node.val, right[1]),
                left[2] + right[2] + 1              // Size includes both subtrees
            };
            
        // Invalid BST: use invalid bounds, keep max size from subtrees
        return new int[]{
            Integer.MIN_VALUE,
            Integer.MAX_VALUE,
            Math.max(left[2], right[2])
        };
    }
}
                

Python Solution:

class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:
        def largest_bst(node: TreeNode) -> List[int]:
            if not node:
                return [float('inf'), float('-inf'), 0]  # [min, max, size]
            
            left = largest_bst(node.left)
            right = largest_bst(node.right)
            
            # Check if current node forms valid BST
            if left[1] < node.val < right[0]:
                return [
                    min(node.val, left[0]),         # Min value
                    max(node.val, right[1]),        # Max value
                    left[2] + right[2] + 1          # Size includes both subtrees
                ]
                
            # Invalid BST: keep track of max size from subtrees
            return [float('-inf'), float('inf'), max(left[2], right[2])]
        
        return largest_bst(root)[2]                 # Return size component
                

C++ Solution:

class Solution {
    vector largestBST(TreeNode* node) {
        // Base case: null represents valid BST
        if (!node) 
            return {INT_MAX, INT_MIN, 0};  // [min, max, size]
        
        vector left = largestBST(node->left);
        vector right = largestBST(node->right);
        
        // Check if current node forms valid BST
        if (node->val > left[1] && node->val < right[0])
            return {
                min(node->val, left[0]),           // Min value
                max(node->val, right[1]),          // Max value
                left[2] + right[2] + 1             // Size includes both subtrees
            };
            
        // Invalid BST: keep track of max size from subtrees
        return {INT_MIN, INT_MAX, max(left[2], right[2])};
    }
    
public:
    int largestBSTSubtree(TreeNode* root) {
        return largestBST(root)[2];                // Return size component
    }
};
                

Complexity:

Time Complexity: O(n), visit each node once
Space Complexity: O(h), recursion stack where h is height

Explanation:

• **Array Information**:
  • [0]: Minimum value in subtree
  • [1]: Maximum value in subtree
  • [2]: Size of largest valid BST
• **Base Case**:
  • Null node returns MAX_VALUE as min
  • MIN_VALUE as max to validate leaf nodes
  • 0 as size for empty tree
• **BST Validation**:
  • Current value must be greater than left max
  • Current value must be less than right min
  • Size accumulates when valid BST found