L53. Largest BST in Binary Tree

Finding the largest Binary Search Tree (BST) in a given binary tree is a classic Data Structures and Algorithms problem. Given the root of an arbitrary binary tree, the objective is to find and return the maximum size (number of nodes) of any subtree that satisfies the strict properties of a valid BST.

1. Defining the Problem and Understanding the Goal

A Binary Search Tree (BST) is a binary tree where for any given node:

• All values in its left subtree are strictly smaller than the node's value.
• All values in its right subtree are strictly greater than the node's value.
• Both the left and right subtrees must also be valid BSTs.

When evaluating an arbitrary binary tree, subtrees lower down might be valid BSTs while parent subtrees might fail the condition.

Real-Life Analogy: The Corporate Hierarchy Audit

Imagine a company hierarchy where every manager must ensure that every single employee in their department (both direct and indirect reports) meets strict salary or performance thresholds: everyone in the left branch must earn less than the manager, and everyone in the right branch must earn more. To find the largest compliant department, you cannot just look from the top down because one non-compliant person at the top invalidates the whole company, even if small regional offices lower down are perfectly structured. Instead, you must audit from the bottom up (branch offices first, then regional offices, then headquarters).

2. Why Do We Need This? (The Status Quo & Naive Approach)

The Naive Brute-Force Approach

If you are asked this in an interview, the immediate brute-force solution relies on your prior knowledge of validating a BST:

1. Visit every node in the binary tree using any standard traversal.
2. Treat each node as the root of a potential subtree and pass it to a validateBST function.
3. If validateBST returns true, calculate the number of nodes in that subtree using a node-counting traversal.
4. Keep track of the maximum size found across all valid subtrees.

Complexity Analysis of Brute Force

• validateBST takes $O(N)$ time.
• Visiting every node takes $O(N)$ time.
• Total Time Complexity: $O(N^2)$ (Quadratic time), which is inefficient for large trees.

Can we do better? Yes, by computing everything in a single bottom-up traversal in $O(N)$ time.

3. Core Mental Model and Better Approach Intuition

To optimize the solution to $O(N)$, we must eliminate redundant checks. When standing at a node, instead of re-scanning its entire left and right subtrees to find minimums and maximums, we can carry information upward from the children to the parent.

To confirm whether a subtree rooted at a node is a valid BST, the parent needs exactly three pieces of information from its left and right children:

1. Largest value in the left subtree (must be strictly less than the current node).
2. Smallest value in the right subtree (must be strictly greater than the current node).
3. Size of the valid BST subtree.

If both children report valid BST metrics and satisfy the bounding conditions, the current node forms a larger valid BST.

4. Designing the Custom Container (NodeValue)

To pass multiple metrics up the recursive call stack cleanly, we encapsulate them in a custom class or struct.

class NodeValue {
public:
    int maxNode;
    int minNode;
    int maxSize;
    
    NodeValue(int minNode, int maxNode, int maxSize) {
        this->minNode = minNode;
        this->maxNode = maxNode;
        this->maxSize = maxSize;
    }
};

Handling Edge Cases (Null Nodes / Leaf Nodes)

• For a Leaf Node: It is automatically a valid BST of size 1. Its minimum value is itself, and its maximum value is itself.
• For a Null / Missing Child: We pass a dummy container:
  • Size: 0
  • Minimum value: INT_MAX (so that any parent comparison correctly views it as smaller/valid).
  • Maximum value: INT_MIN (so that any parent comparison correctly views it as larger/valid).

5. Step-by-Step Post-Order Traversal Strategy

Post-Order traversal (Left -> Right -> Root) is mandatory here because a parent node cannot compute its valid BST status until both its left and right subtrees have fully computed and reported their metrics.

       Root (Current Node)
           /         \
          /           \
     Left Subtree    Right Subtree
     (Evaluated First) (Evaluated Second)

Subtree Validation Logic at Each Node:

1. Left Child Check: Is current.val > left.maxNode?
2. Right Child Check: Is current.val < right.minNode?
3. If Both Conditions Hold (Valid BST):
   • New Min: min(current.val, left.minNode)
   • New Max: max(current.val, right.maxNode)
   • New Size: left.maxSize + right.maxSize + 1
4. If Conditions Fail (Not a BST):
   • Size: max(left.maxSize, right.maxSize)
   • Range Pass-through: Return extreme bounds (INT_MIN and INT_MAX) so that any ancestor above will also fail validation, preventing invalid subtrees from being misidentified as BSTs.

6. Complete Code Implementation

Here is the clean, production-grade implementation matching the optimal approach discussed.

C++ Implementation

class NodeValue {
public:
    int minNode, maxNode, maxSize;
    NodeValue(int minNode, int maxNode, int maxSize) {
        this->minNode = minNode;
        this->maxNode = maxNode;
        this->maxSize = maxSize;
    }
};

class Solution {
private:
    NodeValue largestBSTHelper(TreeNode* root) {
        // Base case: empty tree is a BST of size 0
        if (root == nullptr) {
            return NodeValue(INT_MAX, INT_MIN, 0);
        }
        
        // Post-order traversal: visit left and right children first
        auto left = largestBSTHelper(root->left);
        auto right = largestBSTHelper(root->right);
        
        // Current node is greater than max in left AND smaller than min in right -> Valid BST
        if (root->val > left.maxNode && root->val < right.minNode) {
            return NodeValue(
                min(root->val, left.minNode), 
                max(root->val, right.maxNode), 
                left.maxSize + right.maxSize + 1
            );
        }
        
        // Otherwise, return [-inf, inf] so parent cannot form a valid BST, 
        // and pass along the maximum size found so far in children.
        return NodeValue(INT_MIN, INT_MAX, max(left.maxSize, right.maxSize));
    }

public:
    int largestBST(TreeNode* root) {
        return largestBSTHelper(root).maxSize;
    }
};

Java Implementation

class NodeValue {
    public int minNode;
    public int maxNode;
    public int maxSize;

    public NodeValue(int minNode, int maxNode, int maxSize) {
        this.minNode = minNode;
        this.maxNode = maxNode;
        this.maxSize = maxSize;
    }
}

class Solution {
    private NodeValue largestBSTHelper(TreeNode root) {
        // Base case: empty tree is a BST of size 0
        if (root == null) {
            return new NodeValue(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }

        // Post-order traversal: left and right children first
        NodeValue left = largestBSTHelper(root.left);
        NodeValue right = largestBSTHelper(root.right);

        // Validate BST condition
        if (root.val > left.maxNode && root.val < right.minNode) {
            return new NodeValue(
                Math.min(root.val, left.minNode),
                Math.max(root.val, right.maxNode),
                left.maxSize + right.maxSize + 1
            );
        }

        // If invalid, propagate extreme limits and carry forward max size
        return new NodeValue(Integer.MIN_VALUE, Integer.MAX_VALUE, Math.max(left.maxSize, right.maxSize));
    }

    public int largestBST(TreeNode root) {
        return largestBSTHelper(root).maxSize;
    }
}

7. Complexity Summary Table

8. Summary and Key Takeaways

• Problem Nature: Finding the largest BST requires evaluating subtrees from the bottom up because a violation at a parent node invalidates the entire upper structure.
• Traversal Choice: Post-order traversal is essential because parent nodes require metrics from both left and right children before making calculations.
• Container Pattern: Bundling minNode, maxNode, and maxSize into a custom class/struct allows recursive functions to pass multiple state variables up the call stack cleanly.
• Sentinel Values: Passing INT_MAX for minimums and INT_MIN for maximums on null nodes simplifies boundary comparisons without messy null checks.
• Failure Propagation: When a subtree fails BST validation, passing extreme bounds (INT_MIN, INT_MAX) ensures that any ancestor above will also correctly recognize the failure.
• Optimal Efficiency: The optimized bottom-up approach reduces time complexity from $O(N^2)$ down to $O(N)$.