Watch 10 video solutions for Largest BST Subtree, a medium level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by take U forward has 189,456 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
Note: A subtree must include all of its descendants.
Example 1:
Input: root = [10,5,15,1,8,null,7] Output: 3 Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.
Example 2:
Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1] Output: 2
Constraints:
[0, 104].-104 <= Node.val <= 104
Follow up: Can you figure out ways to solve it with O(n) time complexity?
Problem Overview: You are given a binary tree that is not necessarily a binary search tree. The task is to find the size (number of nodes) of the largest subtree that satisfies the Binary Search Tree property. A subtree counts only if every node inside it follows the BST rule: left values are smaller and right values are larger.
Approach 1: Validate Every Subtree (Brute Force) (Time: O(n^2), Space: O(h))
The direct idea is to treat every node as the root of a potential BST. For each node, run a validation check to confirm whether the subtree rooted at that node satisfies BST rules. The validation function recursively ensures left < root < right while computing the subtree size. If the subtree is valid, update the global maximum size. Because each validation may traverse many nodes repeatedly, the worst-case complexity becomes O(n^2) when the tree is skewed. Space complexity is O(h) due to recursion depth. This approach is straightforward but inefficient for large trees.
Approach 2: Postorder DFS with Subtree Metadata (Optimal) (Time: O(n), Space: O(h))
The optimal solution uses a single postorder traversal from the leaves upward. Each DFS call returns metadata about the current subtree: whether it forms a BST, its size, and the minimum and maximum values inside it. While returning from recursion, you combine the results from the left and right children. A subtree is a valid BST if the left and right subtrees are BSTs and left.max < node.val < right.min. When this condition holds, the subtree size becomes left.size + right.size + 1, and the min/max boundaries are updated accordingly.
If the condition fails, the subtree is marked invalid so its parent cannot treat it as part of a BST. During traversal you maintain a global maximum representing the largest valid BST encountered so far. Each node is processed exactly once, giving O(n) time complexity and O(h) space for recursion. This technique is a classic combination of Depth-First Search and bottom-up state aggregation similar to Dynamic Programming on trees.
The key insight is that every subtree can summarize enough information (min, max, size, validity) for its parent to make a constant-time decision. This avoids repeatedly scanning subtrees. The pattern appears frequently in binary tree problems where parent decisions depend on child properties.
Recommended for interviews: The postorder DFS solution is what interviewers expect. Mentioning the brute force approach first demonstrates understanding of the problem structure. Transitioning to the single-pass postorder solution shows optimization skills and familiarity with bottom-up tree processing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Validate Each Subtree (Brute Force) | O(n^2) | O(h) | Good for understanding the problem and small trees where repeated validation cost is acceptable |
| Postorder DFS with Min/Max Tracking | O(n) | O(h) | Best general solution. Processes each node once and scales well for large trees |