[LC Walkthrough] 669. Trim a Binary Search Tree

Hello world! This is the third article of LeetCode Walkthrough where I record my thinking process to the solution to LeetCode problems.

Today, I’ll be writing 669. Trim a Binary Search Tree. This is the second question of February LeetCoding Challenge 2021.

For this problem, we are asked to trim the given binary search tree so that all nodes have values falling in the range of given low and high values.

As a quick reminder, for binary search trees, when given a root node, all nodes that have smaller value than the root node will fall under the left subtree whereas nodes that have bigger value will fall under the right subtree.

Whenever I see a tree traversal question like this, it’s my primal instinct to solve it with a recursive approach.

The first step to the approach is to think about the base case. When should our recursive method terminate? The answer to this is simple for this question; when the given node is null. We can’t work with a null node, so for this case we can simply return null node.

The next step is to think about possible scenarios. For this problem, a given node can fall into 3 cases:

1. The node’s value falls under the [low, high].
2. The node’s value is smaller than low value.
3. The node’s value is bigger than high value.

For the first case, since we know that the current node’s value falls under the range, we keep the node and perform recursive calls on the left and right subtrees to trim them.

For the second case, since the current node’s value is smaller than the low value, we return a recursive call on the right subtree. We can forget about the left subtree, because we know that all the values in the left subtree is smaller than the current node’s value; we can guarantee that any nodes in the left subtree won’t fall under the range.

The third case goes exactly the same as the second case except we will return a recursive call on the left subtree. Since we know that all the values in the right subtree is bigger than the current node’s value, we can guarantee that any nodes in the right subtree won’t fall under the range.

With these cases in mind, I came up with the following code:

Cases are re-ordered for better code flow

Let us run a test case:

The time complexity of this solution is O(n) where n = # of nodes in the binary search tree. At worst case, we will have to visit every node to see if they fall under the given range.

The space complexity of this solution is O(n) where n = # of nodes in the binary search tree. There could be cases where the given binary search tree is skewed to left/right. If that’s the case, the recursion stack will grow up to the size of # of nodes.

Thanks for reading!