Trim a BST to a Range

Trim a BST to a Range looks like a tree-surgery problem, but it is really a lesson in using the binary-search-tree ordering to throw away whole subtrees without inspecting them. That move — pruning a half you can prove is hopeless — shows up across BST problems.

The slow way first

The brute-force idea: collect every value into a list, throw away the ones outside the range, then rebuild a balanced BST from what is left. That works, but it ignores the structure you already have — it is O(n) extra space for the list plus the cost of rebuilding, and it does not preserve the original shape.

The better question: while standing on a node, can I prove an entire side is doomed? In a BST, yes. If a node value is below lo, every value in its left subtree is even smaller — all out of range. If a node value is above hi, every value in its right subtree is even larger. Either way a whole subtree can be discarded in one step.

The idea: let the ordering prune for you

Recurse from the root. At each node compare its value to the bounds:

• If node.val < lo, the node and its whole left subtree are too small. The only possibly-valid nodes are to the right, so return trim(node.right).
• If node.val > hi, the node and its whole right subtree are too big. Return trim(node.left).
• Otherwise the node is inside the range — keep it, and recursively trim both children, reattaching whatever each returns.

The key insight: we never inspect the dropped subtree at all. Comparing one value lets us prune many nodes.

Walk through it

Step through the animation with range [1, 3]. Root 3 is inside the range, so it stays. Its left child 0 is below lo, so 0 and its (empty) left side vanish and 0 right subtree — the node 2 — is spliced in as the new left child. Node 2 and its child 1 are both in range. The right child 4 is above hi, so 4 is dropped and the root right child becomes None. What remains: 3 → (left 2 → left 1).

Pseudocode

trim(node, lo, hi):
    if node is None:
        return None
    if node.val < lo:                 # node and its left subtree are too small
        return trim(node.right, lo, hi)
    if node.val > hi:                 # node and its right subtree are too big
        return trim(node.left, lo, hi)
    node.left  = trim(node.left,  lo, hi)   # in range: keep, fix up children
    node.right = trim(node.right, lo, hi)
    return node

The Python solution

def trim_bst(root, lo, hi):
    if root is None:
        return None
    if root.val < lo:
        return trim_bst(root.right, lo, hi)
    if root.val > hi:
        return trim_bst(root.left, lo, hi)
    root.left = trim_bst(root.left, lo, hi)
    root.right = trim_bst(root.right, lo, hi)
    return root

• The root is None check is the base case — an empty subtree trims to nothing.
• root.val < lo: the node is too small, and so is everything in its left subtree, so we discard both and return the trimmed right subtree in its place.
• root.val > hi: symmetric — discard the node and its too-large right subtree, returning the trimmed left subtree.
• If we reach the last block the node is in range, so we keep it and reassign each child to the result of trimming it. Reassigning is what splices a surviving grandchild up when a child is dropped.
• We return root so the parent can reattach this node, completing the rebuild on the way back up.

Complexity

We visit each node at most once, so time is O(n). The only extra memory is the recursion stack, which goes as deep as the tree height h — O(log n) for a balanced BST, O(n) in the worst case.

When this pattern shows up

Practice