Trim a Binary Search Tree BST

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:

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

      1         1
    /   \   =>   \
   0     2        2

Output: [1,null,2]

Example 2:

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

Java

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;
}

Problem#

Examples#

Solution#

Method 1 - Preorder DFS#

Code#

Java#