Largest BST Subtree
Understanding the Problem
We have a binary tree (not necessarily a BST), and we need to find the largest subtree within it that satisfies all BST properties. The "size" of a subtree is the total number of nodes in it, and we want to maximize that count.
One point matters for the definition: a "subtree" rooted at some node includes that node and all of its descendants. We are not looking for arbitrary subsets of nodes that form a BST. We need a contiguous subtree, rooted at some node, where every node in that subtree obeys the BST ordering rules.
Whether a subtree rooted at node X is a valid BST depends on information from both its left and right children. All values in the left subtree must be strictly less than X's value, and all values in the right subtree must be strictly greater. This points to a bottom-up approach: gather information from the children first, then decide at the parent whether the combined subtree is a valid BST.
Key Constraints:
0 <= number of nodes <= 10^4→ An O(n^2) approach passes within these bounds, but an O(n) single-pass solution is the target.-10^4 <= Node.val <= 10^4→ Values fit in a 32-bit signed integer, so node values themselves do not overflow. The care needed is in the sentinel values used for min/max tracking, which must compare correctly against any value in this range.
Approach 1: Brute Force (Validate Each Node)
Intuition
For every node in the tree, check whether the subtree rooted at that node is a valid BST. If it is, count its nodes. Track the maximum count across all nodes.
To validate whether a subtree is a BST, we can use the classic approach of passing down an allowed range. A node is valid if its value falls within the range, and both its left and right subtrees are also valid within their updated ranges. Counting nodes in a subtree is a separate DFS.
This works, but it is wasteful. For a node near the root, we validate its entire subtree. Then for its children, we re-validate large portions of the same subtree again. There is a lot of repeated work.
Algorithm
- Define a helper
isValidBST(node, min, max)that returns true if the subtree rooted atnodeis a valid BST where all values are strictly betweenminandmax. - Define a helper
countNodes(node)that returns the number of nodes in the subtree rooted atnode. - For each node in the tree (via any traversal), call
isValidBSTon it. If it returns true, callcountNodesand update the global maximum. - Return the global maximum.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). In the worst case (a skewed tree), we call
largestBSTSubtreeon every node, and for each node we traverse its entire subtree to validate. This gives n + (n-1) + ... + 1 = O(n^2) work. - Space Complexity: O(n). The recursion stack can go up to O(n) deep for a skewed tree.
The repeated validation is the source of the O(n^2) cost. The next approach validates and counts in a single bottom-up pass, gathering information from children and combining it at each parent.
Approach 2: Post-Order Traversal (Optimal)
Intuition
Instead of re-validating each subtree from the top, we gather information from the bottom up so every node is touched once.
In a post-order traversal, we process the left child, then the right child, then the current node. If each child returns three things, whether its subtree is a valid BST, the size of that BST, and the min and max values in its subtree, then at the current node we can decide in O(1) whether the combined subtree is still a valid BST.
Specifically, the subtree rooted at node X is a valid BST if:
- The left subtree is a valid BST, AND the max value in the left subtree is less than X's value.
- The right subtree is a valid BST, AND the min value in the right subtree is greater than X's value.
If both conditions hold, the entire subtree rooted at X is a valid BST with size = leftSize + rightSize + 1. If either fails, X's subtree is not a BST, but we still track the best BST size we found in the children.
To encode all this cleanly, each recursive call returns a tuple: (size, min, max) where size is the BST size if the subtree is a valid BST, or -1 if it is not. The min and max track the value range of the subtree.
The base case for a null node returns (0, +infinity, -infinity), with min and max inverted. This removes the need for separate leaf handling. A leaf has two null children: its left child reports a max of -infinity, which is below any node value, and its right child reports a min of +infinity, which is above any node value. Both BST checks (leftMax < node.val and rightMin > node.val) therefore pass, so a single leaf is correctly treated as a valid BST of size 1.
The -1 size acts as a not-a-BST flag. Once a subtree fails, its parent sees leftSize == -1 or rightSize == -1 and also returns -1, so the failure propagates up: no ancestor can form a valid BST through an invalid child. The largest valid BST seen so far is held in a separate variable, so valid BSTs nested inside an invalid subtree are still recorded before the -1 propagates past them.
Algorithm
- Define a recursive helper that performs post-order traversal and returns
(bstSize, minValue, maxValue)for each subtree. - Base case: For a null node, return
(0, +infinity, -infinity). The inverted min/max ensures any parent node's value will satisfy the BST check. - Recursive case: Get
(leftSize, leftMin, leftMax)from the left child and(rightSize, rightMin, rightMax)from the right child. - If
leftSize != -1andrightSize != -1andleftMax < node.valandrightMin > node.val, then this subtree is a valid BST. Return(leftSize + rightSize + 1, min(leftMin, node.val), max(rightMax, node.val)). - Otherwise, return
(-1, 0, 0)to signal this subtree is not a valid BST. Update the global maximum withmax(leftSize, rightSize). - After traversal, return the global maximum.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once in the post-order traversal. At each node, we do O(1) work: a few comparisons and arithmetic operations.
- Space Complexity: O(n). The recursion stack can go up to O(n) deep for a skewed tree. For a balanced tree, this is O(log n).