Largest BST Subtree

Largest BST Subtree

1. What is this problem about?

The Largest BST Subtree problem asks you to find the size of the largest subtree that is also a valid Binary Search Tree (BST). A subtree of a tree $T$ is a tree consisting of a node in $T$ and all of its descendants. A valid BST is defined by the property that for every node, all values in its left subtree are strictly smaller, and all values in its right subtree are strictly larger. The goal is to return the number of nodes in the largest such subtree.

2. Why is this asked in interviews?

This is a classic Binary Search Tree, Depth-First Search interview pattern question often seen at Microsoft and Meta. It's designed to test a candidate's ability to perform "bottom-up" tree traversal. A naive approach would be to check if each node is the root of a BST, which requires multiple passes over the tree. The optimized solution requires passing multiple pieces of information up the recursion stack, testing a candidate's mastery of recursion and state management.

3. Algorithmic pattern used

The most efficient approach uses Depth-First Search (DFS) with Post-order Traversal. To determine if a node's tree is a BST, we need information from its children:

1. Is the left subtree a BST?
2. Is the right subtree a BST?
3. What is the maximum value in the left subtree?
4. What is the minimum value in the right subtree?
5. What is the size of the subtree?

By returning a tuple or object containing these five values, a parent node can decide in $O(1)$ if it forms a larger BST with its children. If node.val > left_max and node.val < right_min, and both children are BSTs, then the current node is also a BST of size left_size + right_size + 1.

4. Example explanation

Consider a tree:

    10
   /  \
  5    15
 / \     \
1   8     7

• For node 1: It's a BST (size 1, min 1, max 1).
• For node 8: It's a BST (size 1, min 8, max 8).
• For node 5: 5 > 1 (left max) and 5 < 8 (right min). Both children are BSTs. So, node 5 is a BST of size $1+1+1 = 3$.
• For node 7: It's a BST (size 1, min 7, max 7).
• For node 15: Its right child (7) is a BST, but 15 < 7 is false. So, node 15 is NOT a BST.
• For node 10: Its left child is a BST, but its right child is not. So, node 10 is NOT a BST. The largest BST subtree is rooted at 5, with size 3.

5. Common mistakes candidates make

• Top-down approach: Checking isBST(node) for every node, leading to $O(N^2)$ complexity.
• Incorrect null handling: Not properly defining the min/max for null nodes (e.g., a null left child should have a max of $-\infty$).
• Incomplete state: Forgetting to communicate that a subtree is NOT a BST to its parent.
• Global variables: Using global variables to track the max size instead of returning it through recursion (though this is sometimes acceptable, it's less elegant).

6. Interview preparation tip

Master post-order traversal for tree problems where the answer for a node depends on its children's properties. Practice problems like "Validate Binary Search Tree" and "Maximum Path Sum" to get comfortable with passing complex state up a recursive call stack.