Trim a Binary Search Tree — LC 669 Recursive Pruning

Problem Statement#

Given the root of a binary search tree and the lowest and highest boundaries low and high, trim the tree so that all its elements lie in [low, high]. Trimming should not change the relative structure of remaining elements. Return the new root.

Constraints:

• The number of nodes is in the range [1, 10^4]
• 0 <= Node.val <= 10^4
• All values are unique
• 0 <= low <= high <= 10^4

Input:  root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Input:  root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

Why This Problem Matters#

LeetCode 669 Trim a Binary Search Tree is a Medium-difficulty interview question asked at Amazon, Google, Apple, and Microsoft. It is a classic test of two BST instincts: (1) using the BST ordering invariant to skip half the tree, and (2) returning the modified subtree from recursion to elegantly rewire parent pointers.

This question separates candidates who write 30 lines with parent pointers and explicit deletes from those who write 8 lines using recursive substitution. Interviewers love watching candidates discover that returning the trimmed root from each call automatically handles all rewiring.

The same pattern recurs in BST insertion, deletion, and balancing operations and in any tree problem where you "transform a subtree and reattach."

The Core Insight#

For each node, three cases:

1. node.val < low: every node in the left subtree is also < low (BST invariant), so discard the entire left subtree and current node — return trim(node.right).
2. node.val > high: every node in the right subtree is also > high, so discard right subtree and current node — return trim(node.left).
3. Otherwise: the current node is valid. Recursively trim both children and reattach: node.left = trim(node.left); node.right = trim(node.right); return node.

The "return value as new subtree pointer" idiom replaces all parent rewiring — the parent's assignment node.left = trim(...) automatically reflects pruning.

Visual Dry Run#

Tree: [3,0,4,null,2,null,null,1], low = 1, high = 3

       3
      / \
     0   4
      \
       2
      /
     1

Result: [3,2,null,1].

Solution (Optimal)#

class Solution:
    def trimBST(self, root, low, high):
        if not root:
            return None
        if root.val < low:
            return self.trimBST(root.right, low, high)
        if root.val > high:
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

var trimBST = function(root, low, high) {
    if (!root) return null;
    if (root.val < low)  return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);
    root.left  = trimBST(root.left,  low, high);
    root.right = trimBST(root.right, low, high);
    return root;
};

Time: O(n) worst case, O(h) average if much of the tree is discarded. Space: O(h) recursion stack.

Common Mistakes#

• Forgetting to return trim(other_side) when out of range — drops valid descendants.
• Calling trim(root.left) when root.val < low — wastes time; that side is also out of range.
• Trying to delete in-place by setting node.val to null — corrupts the tree shape.
• Treating BST as a generic binary tree — misses the prune-half optimization.
• Not handling root being trimmed away — the function must return None if root itself is out of range.

Interview Tips#

• Mention the BST invariant explicitly: "Because it's a BST, when val < low, the entire left subtree is also < low."
• Use the "return trimmed subtree" idiom — it lets the caller reassign node.left or node.right cleanly.
• Confirm boundaries are inclusive: [low, high] means low and high are kept.
• Discuss complexity: O(n) worst case but typically much less when many values are out of range.

Follow-up Questions#

• Iterative version? Walk down to find the new root, then iteratively trim each side.
• What if input is a generic binary tree (not BST)? Must traverse all nodes — O(n).
• Track deleted node count? Increment a counter in each pruning branch.
• Range query (sum nodes in [low, high]) without modifying? LC 938 — same DFS structure.
• Persistent trim? Build a new tree leaving the original intact.

Key Takeaways#

• LeetCode 669 is a Medium-difficulty FAANG BST question asked at Amazon, Google, and Apple.
• The optimal pattern uses BST ordering: when node.val < low, prune entire left side and current node.
• Use the "return modified subtree" idiom for clean rewiring without parent pointers.
• Time complexity O(n) worst case, often closer to O(h) when pruning helps.
• Space complexity O(h) for recursion.
• The pattern transfers to BST insertion, deletion, and LC 938 Range Sum BST.
• Without exploiting the BST invariant, the solution becomes O(n) for a generic binary tree.