Trim a Binary Search Tree

Med

#0623Time: 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: 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.1 company

Algorithms

Depth-First Search

Data structures

Tree Binary Tree Binary Search Tree

Companies

josh technology

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public TreeNode trimBST(TreeNode root, int low, int high) {6        List<Integer> sortedValues = new ArrayList<>();7        inorder(root, sortedValues);8 9        List<Integer> filteredValues = new ArrayList<>();10        for (int val : sortedValues) {11            if (val >= low && val <= high) {12                filteredValues.add(val);13            }14        }15 16        return buildTree(filteredValues, 0, filteredValues.size() - 1);17    }18 19    private void inorder(TreeNode node, List<Integer> list) {20        if (node == null) {21            return;22        }23        inorder(node.left, list);24        list.add(node.val);25        inorder(node.right, list);26    }27 28    private TreeNode buildTree(List<Integer> list, int start, int end) {29        if (start > end) {30            return null;31        }32        int mid = start + (end - start) / 2;33        TreeNode node = new TreeNode(list.get(mid));34        node.left = buildTree(list, start, mid - 1);35        node.right = buildTree(list, mid + 1, end);36        return node;37    }38}

Complexity

Time

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

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.

Trade-offs

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.

This approach uses recursion to trim the tree in-place. It leverages the properties of a Binary Search Tree (BST) to efficiently decide which parts of the tree to discard. The function recursively processes nodes, returning the new root of the valid subtree.

Algorithm

1. Define a recursive function trimBST(node, low, high).
1. Base Case: If node is null, return null.
1. Recursive Step:
- a. If node.val < low, the current node and its left subtree are invalid. The valid tree must be in the right subtree. Return the result of trimBST(node.right, low, high).
- b. If node.val > high, the current node and its right subtree are invalid. The valid tree must be in the left subtree. Return the result of trimBST(node.left, low, high).
- c. If low <= node.val <= high, the current node is valid. Recursively trim its left and right subtrees by setting node.left = trimBST(node.left, low, high) and node.right = trimBST(node.right, low, high).
- d. Return the current node.

Walkthrough

The core idea is to have a recursive function that takes a node and the bounds low and high, and returns the root of the trimmed subtree. When considering a node, there are three possibilities:

node.val < low: The current node's value is too small. Because it's a BST, all nodes in the left subtree are also too small and can be discarded. The correct replacement for this node must come from its right subtree, as it might contain nodes with values in the valid range. So, we make a recursive call on the right child: trimBST(node.right, low, high).
node.val > high: The current node's value is too large. Symmetrically, all nodes in the right subtree are also too large and can be discarded. The correct replacement must come from the left subtree. We make a recursive call on the left child: trimBST(node.left, low, high).
low <= node.val <= high: The current node is valid and should be kept. However, its children might not be. We need to trim the left and right subtrees. We do this by recursively calling the function on the left and right children and updating the node's left and right pointers with the results: node.left = trimBST(node.left, low, high) and node.right = trimBST(node.right, low, high). After trimming its subtrees, the node itself is returned. The base case for the recursion is when a node is null, in which case we simply return null.

1class Solution {2    public TreeNode trimBST(TreeNode root, int low, int high) {3        if (root == null) {4            return null;5        }6 7        // If the root's value is less than low, the root and its left subtree are discarded.8        // The result must be in the right subtree.9        if (root.val < low) {10            return trimBST(root.right, low, high);11        }12 13        // If the root's value is greater than high, the root and its right subtree are discarded.14        // The result must be in the left subtree.15        if (root.val > high) {16            return trimBST(root.left, low, high);17        }18 19        // If the root's value is within the range, it's a valid node.20        // We recursively trim its left and right subtrees.21        root.left = trimBST(root.left, low, high);22        root.right = trimBST(root.right, low, high);23 24        return root;25    }26}

Complexity

Time

O(N), where N is the number of nodes in the tree. In the worst case, we visit each node exactly once.

Space

O(H), where H is the height of the tree, for the recursion call stack. In a balanced tree, this is O(log N). In the worst case of a skewed tree, it can be O(N).

Trade-offs

Pros

Highly efficient in both time and space.
Modifies the tree in-place by rearranging pointers, avoiding the overhead of creating new nodes.
The code is concise and elegant, directly reflecting the logic of the problem.

Cons

For extremely deep, unbalanced trees, the recursion depth could potentially lead to a stack overflow, though this is rare with typical constraints.

Solutions

Solution

1/** * 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 ; } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} low * @param {number} high * @return {TreeNode} */ var trimBST =2  function (root, low, high) {3    function dfs(root) {4      if (!root) {5        return root;6      }7      if (root.val < low) {8        return dfs(root.right);9      }10      if (root.val > high) {11        return dfs(root.left);12      }13      root.left = dfs(root.left);14      root.right = dfs(root.right);15      return root;16    }17    return dfs(root);18  };

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * trimBST ( TreeNode * root , int low , int high ) { if ( ! root ) 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 ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def trimBST ( self , root : Optional [ TreeNode ], low : int , high : int ) -> Optional [ TreeNode ]: def dfs ( root ): if root is None : return root if root . val > high : return dfs ( root . left ) if root . val < low : return dfs ( root . right ) root . left = dfs ( root . left ) root . right = dfs ( root . right ) return root return dfs ( root )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem