Trim a Binary Search Tree

MEDIUM

Description

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.

Example 1:

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

Example 2:

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

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
0 <= Node.val <= 10⁴
The value of each node in the tree is unique.
root is guaranteed to be a valid binary search tree.
0 <= low <= high <= 10⁴

Approaches

Checkout 2 different approaches to solve Trim a Binary Search Tree. Click on different approaches to view the approach and algorithm in detail.

In-order Traversal and Rebuild

This approach involves two main steps. First, we perform an in-order traversal of the binary search tree to get a sorted list of all its node values. Second, we filter this list to keep only the values within the [low, high] range. Finally, we construct a new, balanced binary search tree from this filtered list of values.

Algorithm

1. Create an empty list, sortedValues.
1. Perform an in-order traversal of the input BST. For each node visited, add its value to sortedValues.
1. Create another empty list, filteredValues.
1. Iterate through sortedValues. If a value is within the range [low, high], add it to filteredValues.
1. Construct a new BST from filteredValues. This can be done recursively:
- a. The middle element of the list becomes the root.
- b. The left half of the list is used to build the left subtree.
- c. The right half of the list is used to build the right subtree.
1. Return the root of the newly constructed tree.

Start by performing an in-order traversal on the input BST. This traversal visits nodes in ascending order of their values. Store these values in a dynamic array or list. After the traversal, you will have a sorted list of all node values. Iterate through this sorted list and create a new list containing only the elements that are greater than or equal to low and less than or equal to high. With this filtered, sorted list, build a new BST. A common and efficient way to do this is to recursively build a balanced BST. The middle element of the current list segment becomes the root of the subtree. The elements to the left of the middle form the left subtree, and the elements to the right form the right subtree. This process is applied recursively until all elements are placed in the new tree. The root of this newly constructed tree is the final answer.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        List<Integer> sortedValues = new ArrayList<>();
        inorder(root, sortedValues);

        List<Integer> filteredValues = new ArrayList<>();
        for (int val : sortedValues) {
            if (val >= low && val <= high) {
                filteredValues.add(val);
            }
        }

        return buildTree(filteredValues, 0, filteredValues.size() - 1);
    }

    private void inorder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }

    private TreeNode buildTree(List<Integer> list, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = buildTree(list, start, mid - 1);
        node.right = buildTree(list, mid + 1, end);
        return node;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the original tree. The in-order traversal takes O(N), filtering the list takes O(N), and building the new tree from the sorted list takes O(M), where M <= N. Thus, the total time is O(N).Space Complexity: O(N). We need O(N) space to store the values from the in-order traversal and O(M) for the filtered values, where M is the number of nodes in the trimmed tree. The recursion stack for traversal and building takes O(H) and O(log M) respectively. The dominant factor is the O(N) space for the list.

Pros and Cons

Pros:

Simple to understand and implement.
The resulting tree is balanced, which can be an advantage for subsequent operations (though not required by the problem).

Cons:

Inefficient in terms of space. It requires extra space proportional to the number of nodes in the original tree.
Creates a completely new tree instead of modifying the existing one, which involves unnecessary object creation and memory allocation.
Does not fully leverage the BST property during the trimming phase.

Code Solutions

Checking out 4 solutions in different languages for Trim a Binary Search Tree. Click on different languages to view the code.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode trimBST ( TreeNode root , int low , int high ) { if ( root == null ) { return root ; } if ( root . val > high ) { return trimBST ( root . left , low , high ); } if ( root . val < low ) { return trimBST ( root . right , low , high ); } root . left = trimBST ( root . left , low , high ); root . right = trimBST ( root . right , low , high ); return root ; } }

Video Solution

Watch the video walkthrough for Trim a Binary Search Tree

Algorithms:

Depth-First Search

Data Structures:

TreeBinary TreeBinary Search Tree

Companies:

josh technology |