Trim a Binary Search Tree
Problem Description
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
Example 2:
Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Constraints:
- The number of nodes in the tree is in the range [1, 104].
- 0 <= Node.val <= 104
- The value of each node in the tree is unique.
rootis guaranteed to be a valid binary search tree.- 0 <= low <= high <= 104
Solve it on LeetCode
Approaches
1. Recursive DFS
Intuition:
The idea is to recursively traverse the tree and rebuild it by considering the constraints of a binary search tree (BST). For each node:
- If the node's value is less than
low, then discard the left subtree (because all values in the left subtree are also less thanlow) and trim the right subtree. - If the node's value is greater than
high, discard the right subtree and trim the left subtree. - If the node's value is within the range
[low, high], then keep the node and recursively trim both its left and right subtrees.
The base case for the recursion is when a null node is encountered.
Code:
- Time Complexity: O(N) where N is the number of nodes in the tree. Each node is visited once.
- Space Complexity: O(N) for the recursion stack in the worst-case scenario, which is a completely unbalanced tree.
2. Iterative DFS with Stack
Intuition:
This approach uses an iterative Depth-First Search (DFS) strategy with a stack to avoid the recursion overhead. The idea is the same as the recursive approach, but maintains a stack to process the nodes iteratively.
- Initialize a stack and push the root node.
- Pop elements from the stack, check if the current node is within the range, and adjust its children nodes accordingly.
- Continue while the stack is not empty.
Code:
- Time Complexity: O(N) since we process each node once.
- Space Complexity: O(N) due to the stack which in the worst case can grow as large as the number of nodes in the tree.