# 669. Trim a Binary Search Tree
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.
Example 1:
Input:
1
/ \
0 2
L = 1
R = 2
Output:
1
\
2
Example 2:
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
# Solution
Approach 1: recursive.
Approach 2: iterative.
# Code (Python)
Approach 1:
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
# recursive
if not root:
return None
if root.val < L:
return self.trimBST(root.right, L, R)
if root.val > R:
return self.trimBST(root.left, L, R)
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
return root
Approach 2:
def trimBST(self, root, L, R):
# iterative
if not root:
return None
# find the root node to return
while root and root.val < L or root.val > R:
if root.val < L:
root = root.right
if root.val > R:
root = root.left
if root.val < L or root.val > R:
return None
# trim left subtree
node = root
while node:
while node.left and node.left.val < L:
node.left = node.left.right # only the right subtree has the chance to fit into the range
node = node.left # subsequent subtrees
# trim right subtree
node = root
while node:
while node.right and node.right.val > R:
node.right = node.right.left
node = node.right
return root
# Code (C++)
Approach 1:
Approach 2: