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.
We can utilize the properties of a BST to perform a recursive traversal. The strategy here involves:
low, we need to trim the left subtree and consider the right subtree.high, we trim the right subtree and consider the left subtree.low, high], we recursively trim both subtrees.The recursive function trimBST checks if the node is NULL. If the node's value is less than low, it trims the left subtree. If the node's value is greater than high, it trims the right subtree. Otherwise, it recursively processes both subtrees.
Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once.
Space Complexity: O(h), where h is the height of the tree, representing the recursion stack.
This iterative approach uses a stack to traverse the tree. The main idea is to mimic the recursive depth-first search using an explicit stack.
Instead of using recursion, this C++ implementation uses a stack to perform depth-first search-like traversal. It adjusts the nodes based on their values compared to the bounds low and high, ensuring all nodes in the stack are within the bounds.
Time Complexity: O(n), as each node is processed once.
Space Complexity: O(h), where h is the height of the tree, due to the stack usage.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
| Approach | Complexity |
|---|---|
| Recursive Trimming with BST Properties | Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once. |
| Iterative Approach Using a Stack | Time Complexity: O(n), as each node is processed once. |
| Default Approach | — |
| 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. |
Trim a Binary Search Tree - Leetcode 669 - Python • NeetCode • 22,801 views views
Watch 9 more video solutions →Practice Trim a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode