Largest BST Subtree - Video Solutions

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.