Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

Input: root = [1,0,2], low = 1, high = 2

      1         1
    /   \   =>   \
   0     2        2

Output: [1,null,2]

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3

     3                3
   /   \             /
  0     4           2
   \               /
    2             1
   /      
  1         

Output: [3,2,null,1]

Solution

Method 1 - Preorder DFS

We can actually do the preorder traversal. For each parent node,

  • if value is less than low, we go to right child
  • if value is more than right, we go to left child
  • Otherwise, if value is in range, we try to trim both left and right children

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public TreeNode trimBST(TreeNode root, int low, int high) {
	if (root == null) {
		return null;
	}
	
	if (root.val > high) {
		return trimBST(root.left, low, high);
	}
	
	if (root.val < low) {
		return trimBST(root.right, low, high);
	}

	// if none of the above is true
	root.left = trimBST(root.left, low, high);
	root.right = trimBST(root.right, low, high);
	return root;
}