Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input:
1
/ \
0 2
L = 1
R = 2
Output:
1
\
2
Example 2:
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
Intuition
Let trim(node) be the desired answer for the subtree at that node. We can construct the answer recursively.
Algorithm
When , we know that the trimmed binary tree must occur to the left of the node. Similarly, when , the trimmed binary tree occurs to the right of the node. Otherwise, we will trim both sides of the tree.
Complexity Analysis
Time Complexity: , where is the total number of nodes in the given tree. We visit each node at most once.
Space Complexity: . Even though we don't explicitly use any additional memory, the call stack of our recursion could be as large as the number of nodes in the worst case.
Analysis written by: @awice