Trim a Binary Search Tree

MediumBinary Search Tree · Recursion🧩 Ordered Set (TreeMap)LeetCode #669 ↗Updated Oct 30, 2026

Problem

Given the root of a binary search tree and a range [low, high], delete every node whose value falls outside the range and return the new root. Surviving nodes must keep their relative structure: if one survivor was a descendant of another, it still is. The trimmed tree is unique.

Inputroot = [1,0,2], low = 1, high = 2Output[1,null,2]

Inputroot = [3,0,4,null,2,null,null,1], low = 1, high = 3Output[3,2,null,1]

Inputroot = [5,3,8], low = 9, high = 12Output[]

1 ≤ nodes ≤ 10⁴ · 0 ≤ Node.val ≤ 10⁴, all distinct · 0 ≤ low ≤ high ≤ 10⁴

Try it yourself

Java

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

If a node is below low, it and its whole left subtree are gone — the answer for that spot is the trimmed right subtree (and vice versa above high). Only the two boundary paths of the tree ever need rewiring.

PatternOrdered Set (TreeMap)

Instinct Keys keep arriving or leaving and you must ask "what is the nearest key below/above x?" or "current min/max" each time - reach for TreeMap/TreeSet.

Memory hack A HashMap with a sense of direction - floor looks down, ceiling looks up, and both answer in log time while the data keeps changing.

Open the Ordered Set (TreeMap) guide →

Approaches

Brute ForceFilter Pre-order, Rebuild by Insertion

Time O(n · h)Space O(n)

Record the in-range values in pre-order, then insert them one by one into an empty BST. A BST is fully determined by the pre-order sequence of its values, and removing nodes keeps the survivors' pre-order order intact, so the rebuild yields exactly the trimmed shape.

Java

public TreeNode trimBST(TreeNode root, int low, int high) {
    List<Integer> kept = new ArrayList<>();
    preorder(root, low, high, kept);
    TreeNode res = null;
    for (int v : kept) res = insert(res, v);
    return res;
}
private void preorder(TreeNode node, int low, int high, List<Integer> kept) {
    if (node == null) return;
    if (node.val >= low && node.val <= high) kept.add(node.val);
    preorder(node.left, low, high, kept);
    preorder(node.right, low, high, kept);
}
private TreeNode insert(TreeNode root, int v) {
    TreeNode node = new TreeNode(v);
    if (root == null) return node;
    TreeNode cur = root;
    while (true) {
        if (v < cur.val) {
            if (cur.left == null) { cur.left = node; break; }
            cur = cur.left;
        } else {
            if (cur.right == null) { cur.right = node; break; }
            cur = cur.right;
        }
    }
    return root;
}

Correct but allocates a whole new tree; insertion is O(n²) on a skewed tree.

BetterRecursive Trim

Time O(n)Space O(h)

Return the trimmed version of each subtree. A node smaller than low is replaced by its trimmed right subtree (its left side is even smaller); a node larger than high by its trimmed left subtree. An in-range node keeps itself and re-attaches its two trimmed children.

Java

public TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null) return null;
    if (root.val < low) return trimBST(root.right, low, high);  // drop root + left side
    if (root.val > high) return trimBST(root.left, low, high);  // drop root + right side
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}

Short and clean, but visits every in-range node even though most need no change.

OptimalIterative Boundary Trimming

Time O(h)Space O(1)

First slide the root into the range. After that, a too-small value can only hide on the path of left children, and a too-large one on the path of right children; everything between those paths is already valid. Walk each path once, splicing out offenders by lifting their inner child.

Java

public TreeNode trimBST(TreeNode root, int low, int high) {
    while (root != null && (root.val < low || root.val > high))
        root = root.val < low ? root.right : root.left;
    if (root == null) return null;
    // Left boundary: remove nodes below low
    for (TreeNode cur = root; cur != null; cur = cur.left)
        while (cur.left != null && cur.left.val < low) cur.left = cur.left.right;
    // Right boundary: remove nodes above high
    for (TreeNode cur = root; cur != null; cur = cur.right)
        while (cur.right != null && cur.right.val > high) cur.right = cur.right.left;
    return root;
}

Touches only the two boundary paths with constant memory.

Pro tip

Explain why the middle is safe: once the root is in range, every value between the two boundary paths already lies inside [low, high].

At a glance

Level	Approach	Time	Space
Brute Force	Filter Pre-order, Rebuild by Insertion	`O(n · h)`	`O(n)`
Better	Recursive Trim	`O(n)`	`O(h)`
Optimal	Iterative Boundary Trimming	`O(h)`	`O(1)`

Common pitfalls

Returning null for an out-of-range node — its other subtree may contain valid nodes.
Trimming only the child and forgetting the replacement may itself be out of range (needs a loop or recursion).
Rebuilding a balanced tree from sorted survivors — correct values, wrong structure.

Interview tips

Start from the recursive rule: below range → go right, above range → go left.
Point out the BST property makes whole subtrees disposable without visiting them.
Offer the iterative O(h)-time version as the follow-up for deep or skewed trees.

Pattern

BST range pruning → when a value range lets you discard or keep whole subtrees at once.

My notes saved in this browser