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
- If a node's value is below
low, its entire left subtree is also belowlow, so the answer lies in the right subtree. - Symmetrically for values above
high. - When a node is within range, recurse into both children and keep the node.
- 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
loworhighmust be kept. - Returning
Nonefor 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.