⚡Flashcard Drill➔
NeetCode #456LC-669MediumTrees
← Back to All Problems

#456 · #669 · Trim a Binary Search Tree(修剪二叉搜索树)

📌 Problem Statement & Constraints

Given the root of a binary search tree and bounds low and high, trim the tree so all its values lie in [low, high], preserving the relative structure. Return the new root. Constraints: the number of nodes is in [1, 10^4], 0 <= low <= high <= 10^4.

💡 Core Algorithmic Approaches

  1. If a node's value is below low, its entire left subtree is also below low, so the answer lies in the right subtree.
  2. Symmetrically for values above high.
  3. When a node is within range, recurse into both children and keep the node.
  4. This is O(n) with the BST pruning, and it works because the BST property guarantees whole subtrees can be discarded.

💻 Benchmark Python3 Implementation

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val < low:
            return self.trimBST(root.right, low, high)   # left subtree is all too small
        if root.val > high:
            return self.trimBST(root.left, low, high)    # right subtree is all too large
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) worst case, but typically much less because whole subtrees are pruned.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Recursing into both children when a node is out of range: the whole prunable subtree would be traversed.
  • Using strict comparisons: the bounds are inclusive, so a node equal to low or high must be kept.
  • Returning None for the whole tree when the root is out of range: the answer is the (possibly non-empty) subtree on the appropriate side.
  • Assuming the tree is balanced: the worst case is still O(n).
⚡
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