Given the root of a binary tree (not necessarily a BST), return the number of nodes in the largest subtree that is itself a valid binary search tree. A subtree must include a node and all of its descendants. For a BST here, every left descendant is strictly less and every right descendant strictly greater than the node.
The tree is given in level-order (breadth-first), using null for missing children.
Input: root = [10, 5, 15, 1, 8, null, 7] Output: 3 The subtree [5, 1, 8] is a BST with 3 nodes; the tree as a whole is not (7 < 15 on the right).
Input: root = [2, 1, 3] Output: 3 The entire tree is already a BST.
- The number of nodes is in the range [0, 10^4] - 1 <= Node.val <= 10^5
A single leaf is always a BST of size 1, and any subtree that happens to satisfy the BST property is a candidate. The brute approach says exactly that: at every node, check whether the subtree rooted there is a valid BST, and if so count its nodes — keeping the maximum. Each BST-check and count is O(n), done at n nodes, so it's O(n²).
The optimal approach fixes the redundant re-scanning by working bottom-up. A subtree is a BST iff both children are BSTs and the node's value fits strictly between the maximum of the left subtree and the minimum of the right. So each dfs(node) returns four things: is this subtree a BST, its size, and its min and max values. A parent combines its children's summaries in O(1); the whole thing is a single postorder pass in O(n). Track the best BST size seen.
“Does 'subtree' mean a node plus all its descendants?”
Yes — you can't pick an arbitrary subset.
“Strict or non-strict inequalities?”
Strict here — equal values break the BST property.
Bottom-up, each node reports whether its subtree is a BST plus its size, min, and max.
A node forms a BST when both children are BSTs and its value sits strictly between the left max and the right min.
Worked example — tree [10, 5, 15, 1, 8, null, 7]
subtree at 5: [5,1,8] is a BST -> size 3 subtree at 15: right child 7 < 15 -> NOT a BST subtree at 10: right subtree not a BST -> NOT a BST largest BST = 3
So the answer is at least 1 for any non-empty tree.
lmax < node.val < rmin is the whole condition.
Each node returns (isBST, size, min, max); parents combine in O(1) → O(n).
| Check every subtree | Postorder summary | |
|---|---|---|
| Idea | Validate + count the BST at each node | Return (isBST, size, min, max) bottom-up |
| Time | O(n^2) | O(n) |
| Space | O(height) | O(height) |
Both find the largest valid-BST subtree; the postorder version avoids re-scanning. Full code is in the Approaches selector below.
Key takeaway
Bottom-up, each node returns (isBST, size, min, max). A node is a BST when both children are BSTs and lmax < value < rmin; its size is lsize + rsize + 1. Track the maximum. O(n) time, O(height) space.
dfs(node) -> (isBST, size, min, max)
empty: (true, 0, +inf, -inf)
if L.isBST and R.isBST and L.max < node.val < R.min:
return (true, L.size + R.size + 1, min(L.min,node.val), max(R.max,node.val))
return (false, 0, -inf, +inf)