# 669. Trim a Binary Search Tree

Reference: LeetCode
Difficulty: Easy

## Problem

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.

Note:

Example:

Follow up: Provide an iterative solution that take $O(1)$ space.

## Analysis

Methods:

I tried using inorder traversal, but it does not work well because of the link connection. 1. Recursion
• If the root is not within [L, R], we should replace it by the left or right child. (2 cases)
• If the root is within the range, we should keep the root node.
• Time: $O(N)$ since each node is traversed.
• Space: $O(h)$
2. Iteration
• Iteration solution is tricky.
• We first find the root that is within the range and replace the invalid one.
• Then we check the children and replace them if necessary.
• Time: $O(N)$
• Space: $O(1)$

## Code

Test Case:

### Recursion

Note:

• else is necessary since we have updated the root. We have to check the root again in the next trimBST call.

Another version:

### Iteration

Reference: Java solution, iteration version

The code in the post has a null bug in the code of finding the root. Try out this test case to see the error.

Note:

• When looking for the new root, we may go left or right, so we can’t just separate two directions in two while loops.
• Draw a picture and you can get a more intuitive picture why we handle the children like this. Hone in the properties of BST.

Comment Junhao Wang
a software engineering cat