NeetCode #408LC-333MediumTreesNC Algo100
← Back to All Problems#408 · #333 · Largest BST Subtree(最大 BST 子树)
📌 Problem Statement & Constraints
Given the root of a binary tree, return the size of the largest subtree that is also a binary search tree. Constraints: the number of nodes is in
[0, 10^4], -10^4 <= Node.val <= 10^4.💡 Core Algorithmic Approaches
- A post-order DFS returns, for each subtree,
(size, min, max)if it is a BST, or a sentinel if it is not. - A subtree is a BST when both children are BSTs, the left maximum is less than the node's value, and the right minimum is greater.
- Track the maximum BST size found.
- Returning
Nonefor non-BST subtrees short-circuits the propagation cleanly.
💻 Benchmark Python3 Implementation
class Solution:
def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
self.best = 0
def dfs(node: Optional[TreeNode]):
"""Return (size, min, max) if the subtree is a BST, else None."""
if not node:
return (0, float("inf"), float("-inf")) # neutral identity
l = dfs(node.left)
r = dfs(node.right)
if l is None or r is None:
return None # a child subtree is not a BST
ls, lmin, lmax = l
rs, rmin, rmax = r
if lmax >= node.val or rmin <= node.val:
return None # ordering violated here
size = ls + rs + 1
self.best = max(self.best, size)
return (size, min(lmin, node.val), max(rmax, node.val))
dfs(root)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Using an in-order traversal and tracking the longest increasing run: a longest-increasing run is necessary but not sufficient for a BST (a right subtree can violate an ancestor's bound).
- Returning
Nonebut still using the child's size: the parent must propagate the failure. - Initialising the empty subtree with
(0, 0, 0): that would corrupt the min/max comparisons;(0, +inf, -inf)is the correct identity. - Forgetting to update
self.bestfor leaves: the update happens for every valid subtree, including single nodes.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.