Largest BST Subtree
Find the size of the largest subtree of a binary tree that is a valid binary search tree, by passing each subtree's BST status, size, minimum and maximum up to its parent.
Problem Understanding
Largest BST Subtree (LeetCode 333): given the root of a binary tree, return the number of nodes in the largest subtree that is also a binary search tree. A subtree includes all of a node's descendants.
Examples: root = [10,5,15,1,8,null,7] → 3; root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1] → 2.
The Intuition: Summaries Flow Up
Whether a subtree is a BST depends only on four facts about each child subtree:
- Is it a BST? If either side is not, neither is this one, or any ancestor.
- Its min and max. The left max must be below the node and the right min above it.
- Its size. A valid subtree's size is left + right + 1.
Computing these in post-order makes each node O(1). The min/max bounds are the same idea as Validate Binary Search Tree, and returning several values from each call is the pattern of Return Values in DFS.
Interactive Walkthrough
ABOVE A NODE: SIZE OF THE BST ROOTED THERE, ✗ IF NONE
POST-ORDER
node
:
largest
0
Post-order: each node waits for both children, then decides if its subtree is a BST
Next
1: left max −∞ < 1 < right min +∞, both sides BSTs: a BST of size 1, the largest so far
tree
Each finished node shows the size of the BST rooted at it, or ✗. Try Hidden break: every parent and child look in order, but a value deep in the right subtree breaks the whole tree.
Dry Run Table
Input: root = [10,5,15,1,8,null,7].
| Node (post-order) | Check | Result |
|---|---|---|
| 1 | leaf | BST, size 1 |
| 8 | leaf | BST, size 1 |
| 5 | 1 < 5 < 8 | BST, size 3 (largest so far) |
| 7 | leaf | BST, size 1 |
| 15 | right min 7 ≤ 15 | not a BST |
| 10 | right subtree not a BST | not a BST |
Answer: 3.
The Solution Template
Post-order DFS returning (isBST, size, min, max).
Largest BST Subtree Code
1var largestBSTSubtree = function(root) {2 let best = 0;3 const walk = (node) => {4 if (!node) return [true, 0, Infinity, -Infinity];5 const [lBst, lSize, lLo, lHi] = walk(node.left);6 const [rBst, rSize, rLo, rHi] = walk(node.right);7 if (lBst && rBst && lHi < node.val && node.val < rLo) {8 const size = lSize + rSize + 1;9 best = Math.max(best, size);10 return [true, size, Math.min(lLo, node.val), Math.max(rHi, node.val)];11 }12 return [false, 0, 0, 0];13 };14 walk(root);15 return best;16};
Edge Cases & Common Mistakes
- Empty tree: the answer is 0.
- Duplicates: LeetCode's BST has strictly smaller left and larger right values, so an equal value breaks it.
- Comparing only with direct children: misses violations deeper down; compare with the subtree min and max.
- Returning a subtree's size when it is not a BST: an ancestor could then count nodes from an invalid subtree.
- Extreme values: with INT_MIN/INT_MAX sentinels, a node holding exactly those values needs long or nullable bounds.
Summary
In post-order, each node combines its children's (isBST, size, min, max): it is a BST when both children are and left max < val < right min. Track the largest size. O(n) time, O(h) space.
More practice: DSA interview questions with answers · patterns cheat sheet