Watch 10 video solutions for Trim a Binary Search Tree, a medium level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by NeetCode has 22,801 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.
Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
Example 1:
Input: root = [1,0,2], low = 1, high = 2 Output: [1,null,2]
Example 2:
Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3 Output: [3,2,null,1]
Constraints:
[1, 104].0 <= Node.val <= 104root is guaranteed to be a valid binary search tree.0 <= low <= high <= 104Problem Overview: You receive the root of a binary search tree and two boundaries low and high. The task is to remove every node whose value falls outside this range while preserving the BST structure. The final tree must still satisfy the binary search tree property.
Approach 1: Recursive Trimming with BST Properties (O(n) time, O(h) space)
This approach directly uses the ordering guarantee of a BST. If a node value is smaller than low, the entire left subtree must also be smaller, so you skip it and continue trimming the right subtree. If a node value is greater than high, the entire right subtree can be discarded and you move to the left subtree. Otherwise the node is valid, so recursively trim both children and reconnect them. Each node is visited at most once using depth-first search, giving O(n) time where n is the number of nodes, and O(h) recursion stack space where h is the tree height.
Approach 2: Iterative Approach Using a Stack (O(n) time, O(h) space)
An iterative DFS avoids recursion by maintaining an explicit stack. First adjust the root until it falls within the valid range by moving right when the value is too small or left when it is too large. After fixing the root, traverse the tree with a stack and trim children in place. When a left child is below low, replace it with its right subtree; when a right child exceeds high, replace it with its left subtree. The algorithm still processes each node once, so the time complexity remains O(n). The stack holds at most O(h) nodes, matching the height of the tree.
Recommended for interviews: The recursive BST-based trimming solution is the expected answer in most interviews. It shows that you recognize how BST ordering lets you discard entire subtrees without scanning them individually. The iterative version is useful if the interviewer asks for a non-recursive DFS or wants to discuss stack-based tree traversal, but the recursive approach is usually shorter and easier to reason about under pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Trimming with BST Properties | O(n) | O(h) | Best general solution. Clean logic that leverages BST ordering to discard entire subtrees quickly. |
| Iterative DFS Using Stack | O(n) | O(h) | When recursion depth is a concern or the interviewer asks for an iterative tree traversal. |