LeetCode 669 - Trim a Binary Search Tree

LeetCode Problem 669

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

LeetCode 669, Trim a Binary Search Tree, asks us to modify a binary search tree so that every remaining node has a value within the inclusive range [low, high].

The input consists of three parts:

• root, the root node of a valid binary search tree
• low, the minimum allowed value
• high, the maximum allowed value

A binary search tree, often abbreviated as BST, has an important ordering property:

• Every value in the left subtree is smaller than the current node
• Every value in the right subtree is larger than the current node

The goal is to remove every node whose value falls outside the allowed interval. However, we are not allowed to arbitrarily rebuild the tree. The relative structure of the remaining nodes must stay intact. If a node survives the trimming process, all of its surviving descendants must still appear beneath it in the same relative arrangement.

The returned result is the root of the trimmed tree. One subtle but important detail is that the original root may itself be removed. In that case, one of its descendants becomes the new root.

The constraints tell us several useful things:

• The tree can contain up to 10^4 nodes, which is large enough that inefficient repeated traversals should be avoided.
• All node values are unique.
• The input tree is guaranteed to already satisfy BST ordering rules.
• The bounds satisfy low <= high.

The BST guarantee is the key observation that enables an efficient solution. Without it, we would need to inspect every subtree more carefully because node ordering would not provide any pruning opportunities.

Several edge cases are especially important:

• The root itself may be outside the valid range.
• Every node might be removed.
• No nodes might need removal.
• A node could have only one valid subtree after trimming.
• Deeply skewed trees may create recursion depth concerns in some languages.

A naive implementation that removes nodes without respecting BST structure could accidentally disconnect valid descendants or violate the original parent-child relationships.

Approaches

A brute-force solution would traverse the entire tree and rebuild a completely new BST containing only values within the range. One way to do this is:

1. Perform a traversal of the original tree.
2. Collect every value in [low, high].
3. Insert those values into a new BST.

This approach eventually produces a valid trimmed tree, but it does not preserve the original structure. The problem explicitly requires descendants to remain descendants in the same relative arrangement. Rebuilding the tree from scratch can change the shape of the tree entirely.

Another brute-force variation would recursively inspect every node and manually reconnect subtrees without using BST ordering properties. This works correctly, but it still explores many unnecessary branches because it treats the structure like an arbitrary binary tree.

The key insight for the optimal solution comes directly from the BST ordering property.

Suppose we are currently examining a node:

• If node.val < low, then the entire left subtree must also be smaller than low, because every value in the left subtree is less than the current node. Therefore, the entire left subtree can be discarded immediately.
• If node.val > high, then the entire right subtree must also be larger than high, so the entire right subtree can also be discarded immediately.
• If the current node lies within range, then the node should remain, and we recursively trim both children.

This pruning behavior makes the recursive solution elegant and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Traverses all nodes and may rebuild the tree or store extra values
Optimal	O(n)	O(h)	Uses BST ordering to prune invalid subtrees efficiently

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

1. Start with the current node, initially the root of the tree.
2. If the current node is None, return None.

This is the recursion base case. An empty subtree remains empty after trimming. 3. Check whether the current node's value is smaller than low.

If it is, then both the current node and its entire left subtree must be invalid because all left subtree values are even smaller. Therefore, we discard the current node and recursively process only the right subtree. 4. Check whether the current node's value is larger than high.

If it is, then both the current node and its entire right subtree must be invalid because all right subtree values are even larger. Therefore, we discard the current node and recursively process only the left subtree. 5. If the current node lies within the valid range, keep it.

We now recursively trim both children:

• Assign the trimmed result of the left subtree to node.left
• Assign the trimmed result of the right subtree to node.right

6. Return the current node after its children have been updated.

At this point, the subtree rooted at this node satisfies the trimming requirements.

Why it works

The correctness relies on the BST ordering invariant.

Whenever a node is smaller than low, every node in its left subtree is guaranteed to also be smaller than low, so removing the entire left subtree is always safe. Similarly, whenever a node is larger than high, every node in its right subtree is guaranteed to also be larger than high.

For nodes inside the valid range, recursively trimming the children ensures that every remaining descendant also lies within the range. Because the algorithm only removes invalid nodes and reconnects valid descendants through recursive returns, the original relative structure of the surviving nodes is preserved.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def trimBST(
        self,
        root: Optional[TreeNode],
        low: int,
        high: int
    ) -> Optional[TreeNode]:

        if root is None:
            return None

        if root.val < low:
            return self.trimBST(root.right, low, high)

        if root.val > high:
            return self.trimBST(root.left, low, high)

        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)

        return root

The implementation follows the recursive strategy directly.

The first condition handles the base case. If the subtree is empty, there is nothing to trim, so the function returns None.

The next two conditions implement BST pruning.

When root.val < low, the current node and every node in its left subtree are guaranteed to be invalid. The only possible valid nodes must exist in the right subtree, so the function recursively trims and returns root.right.

When root.val > high, the opposite reasoning applies. The current node and every node in its right subtree are invalid, so the function recursively trims and returns root.left.

If the current node lies within the valid range, we keep the node and recursively trim both children. The recursive calls update root.left and root.right directly so that invalid descendants are removed.

Finally, the current node is returned as the root of the trimmed subtree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }

    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
}

The Go implementation is structurally identical to the Python version.

The primary difference is Go's use of pointers and nil instead of Python references and None. Recursive calls return *TreeNode pointers, which are assigned back into Left and Right.

No special integer overflow handling is necessary because node values are small and comparisons are straightforward.

Worked Examples

Example 1

Input:

root = [1,0,2]
low = 1
high = 2

Tree structure:

    1
   / \
  0   2

Step-by-step traversal:

Current Node	Condition	Action
1	Within range	Keep node, trim both children
0	0 < low	Discard node, return right subtree
None	Base case	Return None
2	Within range	Keep node
None	Base case	Return None

After trimming:

    1
     \
      2

Output:

[1,null,2]

Example 2

Input:

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

Tree structure:

        3
       / \
      0   4
       \
        2
       /
      1

Step-by-step traversal:

Current Node	Condition	Action
3	Within range	Keep node
0	0 < low	Discard node, process right subtree
2	Within range	Keep node
1	Within range	Keep node
4	4 > high	Discard node, process left subtree
None	Base case	Return None

The left subtree becomes:

    2
   /
  1

The right subtree is removed entirely.

Final tree:

      3
     /
    2
   /
  1

Output:

[3,2,null,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited at most once
Space	O(h)	Recursive call stack depends on tree height

The algorithm processes each node a single time. Every recursive call either removes a subtree immediately or continues trimming valid branches. Since no node is revisited, the total running time is linear in the number of nodes.

The auxiliary space complexity comes from recursion depth. In a balanced BST, the height is O(log n). In the worst case, a completely skewed tree has height O(n).

Test Cases

# Helper functions for testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        node = queue.pop(0)

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

# Solution implementation

class Solution:
    def trimBST(self, root, low, high):
        if root is None:
            return None

        if root.val < low:
            return self.trimBST(root.right, low, high)

        if root.val > high:
            return self.trimBST(root.left, low, high)

        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)

        return root

solution = Solution()

# Example 1
root1 = TreeNode(1, TreeNode(0), TreeNode(2))
assert serialize(solution.trimBST(root1, 1, 2)) == [1, None, 2]  # basic trimming

# Example 2
root2 = TreeNode(
    3,
    TreeNode(0, None, TreeNode(2, TreeNode(1))),
    TreeNode(4)
)
assert serialize(solution.trimBST(root2, 1, 3)) == [3, 2, None, 1]  # trims both sides

# Single valid node
root3 = TreeNode(1)
assert serialize(solution.trimBST(root3, 1, 1)) == [1]  # single node retained

# Single invalid node
root4 = TreeNode(0)
assert serialize(solution.trimBST(root4, 1, 2)) == []  # entire tree removed

# Entire left subtree removed
root5 = TreeNode(5, TreeNode(3), TreeNode(7))
assert serialize(solution.trimBST(root5, 5, 7)) == [5, None, 7]  # left subtree discarded

# Entire right subtree removed
root6 = TreeNode(5, TreeNode(3), TreeNode(7))
assert serialize(solution.trimBST(root6, 3, 5)) == [5, 3]  # right subtree discarded

# No trimming needed
root7 = TreeNode(2, TreeNode(1), TreeNode(3))
assert serialize(solution.trimBST(root7, 1, 3)) == [2, 1, 3]  # unchanged tree

# Deep skewed tree
root8 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
assert serialize(solution.trimBST(root8, 2, 3)) == [2, None, 3]  # skewed structure

# Root replaced by descendant
root9 = TreeNode(1, None, TreeNode(2))
assert serialize(solution.trimBST(root9, 2, 2)) == [2]  # new root selected

Test	Why
[1,0,2], range [1,2]	Validates basic left-side trimming
[3,0,4,null,2,null,null,1], range [1,3]	Validates trimming on both sides
Single valid node	Ensures isolated valid nodes remain
Single invalid node	Ensures entire tree can be removed
Entire left subtree removed	Confirms BST pruning works correctly
Entire right subtree removed	Confirms symmetric pruning behavior
No trimming needed	Verifies tree remains unchanged
Deep skewed tree	Tests recursion on unbalanced trees
Root replaced by descendant	Ensures recursive returns correctly update root

Edge Cases

One important edge case occurs when the root itself is outside the valid range. A naive implementation might incorrectly keep the original root or disconnect valid descendants. In this solution, when the root value is smaller than low, the algorithm immediately returns the trimmed right subtree. Similarly, when the root value is larger than high, it returns the trimmed left subtree. This naturally promotes a valid descendant into the new root position.

Another critical case is when an entire subtree must be discarded. Because this is a BST, if a node is too small, every node in its left subtree is also too small. Some incorrect solutions still recursively process that invalid subtree, wasting work or introducing reconnection bugs. This implementation safely skips those subtrees entirely.

A third important edge case is a highly unbalanced tree, such as a linked-list-shaped BST. Recursive tree algorithms can sometimes fail on deep structures if recursion is not carefully implemented. This solution still works correctly because each recursive call processes exactly one subtree and returns a valid trimmed subtree. The only consequence is that the recursion depth may reach O(n) in the worst case.

A final subtle edge case occurs when no trimming is needed at all. Some implementations accidentally reconstruct nodes or alter child references unnecessarily. In this solution, nodes within the valid range are preserved directly, and only their children are recursively updated, so the original structure remains intact.