# 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:**

1 | Input: |

1 | Input: |

**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.

- 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)$

- If the
- 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:**

1 | [1,0,2] |

### Recursion

**Note:**

`else`

is necessary since we have updated the`root`

. We have to check the`root`

again in the next`trimBST`

call.

1 | public TreeNode trimBST(TreeNode root, int L, int R) { |

Another version:

1 | public TreeNode trimBST(TreeNode root, int L, int R) { |

### 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.

1 | [1,0,2] |

**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.

1 | public TreeNode trimBST(TreeNode root, int L, int R) { |

Comment