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.

Removing a node does not 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 still be in range. We cannot drop a whole subtree based on one node. We have to keep the valid parts.

The BST property is what makes the pruning cheap. If a node's value is less than low, then its entire left subtree is also less than low, because every value in the left subtree is smaller than the node. So we can discard the node and its left subtree together, but the right subtree still needs checking. The mirror case applies when a node's value is greater than high.

Key Constraints:

Intuition

Recursion fits this problem because trimming a subtree is the same problem as trimming the whole tree. At each node, we compare its value against the range and one of three cases applies.

If the node's value is less than low, the node is too small, and so is its entire left subtree (every value there is smaller than the node, which is already below low). We discard the node and its left subtree together and recurse only into the right subtree, returning whatever it produces. A node with value 0 might have a right child with value 5, and when low = 1 that 5 belongs in the answer.

The mirror case applies when the node's value exceeds high: the node and its entire right subtree are too large, so we recurse into the left subtree and return that.

If the node's value is within [low, high], we keep it, but its descendants can still be out of range. We recurse into both children, reassign the trimmed subtrees back to root.left and root.right, and return the node.

Each call resolves one node and delegates the rest. The reassignment on the return path rebuilds the tree from the bottom up: a parent always receives the already-trimmed version of its child.

Algorithm

Example Walkthrough

Code

The recursion stack is the only extra space this uses, and it can reach O(n) on a skewed tree. The next approach removes the stack entirely and trims in place with O(1) extra space.

Intuition

The iterative approach applies the same logic as the recursive one without a call stack, split into three phases.

Phase 1 finds a valid root. The current root might be out of range. If it is too small, the valid root can only be in the right subtree, so we move right. If it is too large, we move left. We repeat until we reach a node within [low, high] or run out of nodes.

After Phase 1, every remaining out-of-range node sits on one side: nodes below low can only be in the left subtree, and nodes above high can only be in the right subtree. That lets us clean each side with an independent walk.

Phase 2 walks down the left chain from the root. At each node, while its left child's value is less than low, that child and its own left subtree are too small, so we replace the child with its right subtree, which may still hold valid nodes. We repeat until the left child is in range, then descend.

Phase 3 mirrors Phase 2 on the right chain: while a right child exceeds high, replace it with its left subtree.

Algorithm

Example Walkthrough

Code