We have a BST and a range [low, high]. We need to remove every node whose value falls outside this range, and return the modified tree. The critical requirement is that the relative structure of the remaining nodes stays the same. If node A was an ancestor of node B before trimming, and both survive, then A must still be an ancestor of B after trimming.

What makes this problem interesting is that removing a node doesn't necessarily mean discarding its entire subtree. Consider a node with value 0 when low = 1. The node itself is too small, but its right child (say, value 2) might be perfectly valid. So we can't just chop off a subtree and call it done. We need to selectively keep parts of the tree.

The key observation comes from the BST property. If a node's value is less than low, then its entire left subtree is also less than low (because everything in the left subtree is smaller than the node). So we can safely discard the node and its left subtree, but we still need to check the right subtree. The mirror logic applies when a node's value is greater than high.

Key Constraints:

Intuition

The most natural way to approach this is with recursion. At each node, we ask: "Is this node's value within the range [low, high]?" Based on the answer, three things can happen.

If the node's value is less than low, the node itself is too small. But here's the thing: because of the BST property, the node's entire left subtree is also too small (every value in the left subtree is less than the node, which is already less than low). So we can throw away the node and its left subtree completely. But the right subtree might contain valid nodes. A node with value 0 could have a right child with value 5, and if low = 1, that 5 is perfectly fine. So we recursively trim the right subtree and return whatever survives.

The mirror case applies when the node's value exceeds high. The node and its entire right subtree are too large, but the left subtree might have valid nodes.

If the node's value is within [low, high], we keep it. But its children might still have out-of-range nodes deeper down. So we recursively trim both the left and right subtrees and attach the results.

This recursive approach is clean because each call handles exactly one node and delegates the rest. The tree naturally rebuilds itself from the bottom up as the recursion unwinds.

Algorithm

Example Walkthrough

Code

The recursive approach is already O(n) time, which is optimal. But the recursion stack can grow to O(n) for a skewed tree. What if we could achieve the same result iteratively with O(1) extra space?

Intuition

The iterative approach applies the exact same logic as the recursive one, just without the call stack. The trick is to break the problem into three phases.

First, we need to find a valid root. The current root might be outside the range. If it's too small, we move to its right child. If it's too large, we move to its left child. We keep doing this until we find a node within [low, high] or run out of nodes.

Once we have a valid root, we need to trim nodes that are too small from the left subtree and nodes that are too large from the right subtree. Here's the nice part: we can handle these separately.

For the left subtree, we walk down the left chain. At each node, if its left child has a value less than low, that child and its entire left subtree are too small. So we replace the child with its right subtree (which might contain valid nodes). We keep doing this until all left-side nodes are within range.

The mirror logic applies to the right subtree: walk down the right chain, and whenever a right child exceeds high, replace it with its left subtree.

Algorithm

Example Walkthrough

Code