Trim a Binary Search Tree: Recursive Range Pruning

May 21, 20264 min read

leetcodeproblemmediumtrees

You are given the root of a binary search tree and two integers, low and high. Your job is to trim the tree so that every node's value falls within the inclusive range [low, high]. Trimming doesn't just mean deleting individual nodes. When you remove a node, you need to reattach the valid parts of its subtree so the BST structure is preserved.

This is LeetCode 669: Trim a Binary Search Tree. Consider the example with root = [3, 0, 4, null, 2, null, null, 1], low = 1, and high = 3. Nodes 0 and 4 are outside the range, so they need to go. But node 2 and node 1, which sit below node 0, are perfectly valid and need to survive.

Nodes 0 and 4 fall outside the range [1, 3] and are removed. The trimmed tree keeps only nodes with values between 1 and 3.

Approach

The key insight is that BST ordering tells you everything you need to know at each node. You only have three cases to handle:

If the current node's value is less than low, then this node and its entire left subtree are too small. The only part worth keeping is somewhere in the right subtree. So you skip this node entirely and return the result of trimming the right subtree.
If the current node's value is greater than high, then this node and its entire right subtree are too large. You skip to the left subtree.
If the current node's value is within [low, high], you keep it. But its children might still contain out-of-range nodes, so you recursively trim both the left and right subtrees and reattach the results.

That is the entire algorithm. The BST property guarantees that when root.val < low, nothing in the left subtree can possibly be in range either (all left descendants are even smaller). Same logic applies in the other direction when root.val > high.

Drill BST recursion patterns with spaced repetition

The Python solution

def trimBST(root, low, high):
    if not root:
        return None
    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

Here is what each part does:

Base case: if the node is None, there is nothing to trim. Return None.
Value too small (root.val < low): this node and everything to its left are out of range. Recurse on root.right to find nodes that might still qualify.
Value too large (root.val > high): this node and everything to its right are out of range. Recurse on root.left.
Value in range: keep this node. Recursively trim both subtrees and assign the results back to root.left and root.right. Return the node.

The BST ordering property means you never need to check both subtrees when the current node is out of range. If a node is too small, everything to its left is guaranteed to be even smaller. If a node is too large, everything to its right is guaranteed to be even larger. You can confidently skip an entire branch every time.

Practice tree trimming with interactive flashcards

Visual walkthrough

Let's trace through the recursion on our example tree with low = 1 and high = 3:

Step 1: Visit node 3. Is 1 ≤ 3 ≤ 3? Yes. Keep it and recurse on both subtrees.

Node 3 is inside [1, 3]. We trim its left and right children separately.

Step 2: Visit node 4 (right child of 3). Is 4 ≤ 3? No, 4 is too large. Return trimBST(node.left).

Node 4 is above the range. Its entire right subtree would also be too large. Skip to the left child, which is None.

Step 3: Visit node 0 (left child of 3). Is 0 ≥ 1? No, 0 is too small. Return trimBST(node.right).

Node 0 is below the range. Its left subtree would also be too small. Skip to the right child: node 2.

Step 4: Visit node 2. Is 1 ≤ 2 ≤ 3? Yes. Keep it and recurse on both subtrees.

Node 2 is inside [1, 3]. It becomes the new left child of node 3 (replacing node 0).

Step 5: Visit node 1. Is 1 ≤ 1 ≤ 3? Yes. Keep it. No children to recurse on. Done!

Node 1 is inside [1, 3]. The final trimmed tree is 3 → 2 → 1.

Complexity analysis

Metric	Value	Why
Time	O(n)	Visit each node at most once
Space	O(h)	Recursion stack depth equals tree height

In the worst case (a skewed tree), h = n, so space could be O(n). For a balanced tree, space is O(log n).

Building blocks

This problem combines two fundamental patterns you will see over and over in tree problems:

BST range checking: using the BST ordering property to make decisions without exploring both subtrees. This is the same idea behind validating a BST or searching for a value in a BST.
Recursive tree modification: returning a (possibly different) node from each recursive call and assigning it back to the parent's child pointer. This "return the new subtree root" pattern is how you structurally change a tree without losing nodes.

Once you internalize these two building blocks, problems like deleting a node in a BST or converting a BST to a greater tree become much more approachable.

Edge cases

Empty tree: root is None, return None immediately.
All nodes in range: every node passes the range check, so the tree comes back unchanged.
All nodes out of range: every node gets skipped, and you end up returning None.
Single node: just check whether that one value falls within [low, high]. If yes, return it. If no, return None.

From understanding to recall

You can read through this solution and understand it in a few minutes. But if someone asks you to write it from scratch in a week, will you remember the three cases? Will you remember which subtree to recurse into when a node is too small versus too large? The gap between "I understand it" and "I can reproduce it" is where spaced repetition comes in. Drilling this pattern at increasing intervals locks the decision logic into long-term memory, so you can write it confidently without re-deriving it each time.

Validate Binary Search Tree - Uses the same BST range-checking pattern
Delete Node in a BST - Another recursive BST modification
Convert BST to Greater Tree - Recursive BST traversal with modification

Try CodeBricks free