Leetcode[669] Trim a Binary Search Tree

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.

Difficulty

• Level: Medium
• Acceptance: 64.2%

Solution

Time Complexity: O(n), Space Complexity: O(n)

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.