⚡Flashcard Drill➔
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

  1. A post-order DFS returns, for each subtree, (size, min, max) if it is a BST, or a sentinel if it is not.
  2. 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.
  3. Track the maximum BST size found.
  4. Returning None for 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 None but 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.best for 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems