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
\nLet trim(node) be the desired answer for the subtree at that node. We can construct the answer recursively.
Algorithm
\nWhen , 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.
\n\nComplexity Analysis
\nTime Complexity: , where is the total number of nodes in the given tree. We visit each node at most once.
\nSpace 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.
\nAnalysis written by: @awice
\n