Given the
root
of a binary search tree and the lowest and highest boundaries aslow
andhigh
, 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.
Difficulty
- Level: Medium
- Acceptance: 64.2%
Solution
Analysis
I solved this problem using recursion which calls upon the function again for the left and right node until the function reaches the furthest child nodes.
From there, it will evaluate the nodes to see if the value is lower than or greater than the low
and high
range given. If it is lower, the node will now be root.right
since anything left of that node will be lower than the value of the node itself and hence lower than low
. The same principle applies if the node’s value is higher than high
and we will set the node as root.left
instead.