669. Trim a Binary Search Tree


Problem Description

The problem presents a binary search tree (BST) and requires one to trim the tree such that all the nodes contain values between two boundaries: low and high (inclusive). After trimming, the resulting tree should still be a valid BST, and the relative structure of the remaining nodes should be the same. This means that if a node is a descendant of another in the original tree, it should still be a descendant in the trimmed tree. Importantly, the values that remain in the tree should fall within the specified range, which may also result in a new root being chosen if the original root does not meet the criteria.

Intuition

To arrive at the solution, we need to leverage the properties of a BST, where the left child is always less than the node, and the right child is always greater than the node. We perform a depth-first search (DFS) traversal of the tree and make decisions at each node:

  • If the current node's value is less than low, it means that this node and all nodes in its left subtree are not needed because their values will also be less than low. Thus, we recursively trim the right subtree because there can be valid values there.

  • Conversely, if the current node's value is greater than high, the current node and all nodes in its right subtree won't be needed since they'll be greater than high. So, we recursively trim the left subtree.

  • If the current node's value falls within the range [low, high], it is part of the solution tree. We then apply the same trimming process to its left and right children, updating the left and right pointers as we do so.

The recursive process will traverse the tree, and when it encounters nodes that fall outside the [low, high] range, it effectively 'removes' them by not including them in the trimmed tree. Once the trimming is complete, the recursive function will return the root of the now-trimmed tree, which may or may not be the same as the original root, depending on the values of low and high.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of these properties could exist for a graph but not a tree?

Solution Approach

The solution uses a recursive approach to implement the depth-first search (DFS) algorithm for the binary search tree. The goal of the DFS is to visit every node and decide whether to keep it in the trimmed tree based on the low and high boundaries. The base case for the recursion is when a None (null) node is encountered, indicating that we have reached a leaf's child or a node has been removed because it's outside [low, high].

Upon visiting each node, we perform the following steps:

  • First, we check if the current node's value is greater than high. If it is, we know that we won't need this node or any nodes in its right subtree, so we only return the result of the recursive call on the node's left child.

  • If the current node's value is less than low, we perform the opposite action. We return the result of the recursive call on the node's right child because the left subtree would contain values that are also too low.

  • For nodes that have values within the [low, high] range, we apply the recursive trimming process to both children, and then we return the current node, as it satisfies the range conditions.

Here's the implementation of the algorithm:

1def dfs(root):
2    if root is None:
3        return root
4    if root.val > high:
5        return dfs(root.left)
6    if root.val < low:
7        return dfs(root.right)
8    root.left = dfs(root.left)
9    root.right = dfs(root.right)
10    return root

The dfs function is defined within the main class method trimBST. We then call dfs(root) to begin the recursive trimming process from the root of the given tree.

This recursive function significantly simplifies the process of traversing and modifying the tree, as it leverages the call stack to keep track of the nodes being processed and utilizes the recursion's inherent backtracking mechanism to connect the remaining nodes in the correct structure.

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary search tree, since in the worst case, we may have to visit all nodes. The space complexity is O(H), where H is the height of the tree, due to the space used by the recursion stack during the depth-first search (it may become O(N) in the case of a skewed tree).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. We have the following BST and we want to trim it so that all node values are between low = 1 and high = 3:

1        4
2       / \
3      2   6
4     / \   
5    1   3   

We start at the root:

  1. The root node has a value 4, which is greater than high. According to the algorithm, we won't need this node or any in its right subtree, so we now move to its left child 2.

  2. Node 2 falls within our range [low, high]. Therefore, we need to check both of its children.

    • The left child 1 is within the range and ends up being a leaf in our trimmed tree.
    • The right child 3 is also within the range and is kept.

Since 2 falls within the range and both of its children are kept, 2 becomes the new root of our trimmed BST.

The trimmed BST looks like this:

1    2
2   / \
3  1   3

All nodes are within the range [1, 3], and the tree structure for these nodes is maintained relative to each other. Thus, the trimming process is complete. The recursive calls have assessed and made decisions at every node, leading to this valid trimmed BST.

Not Sure What to Study? Take the 2-min Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Python Solution

1class TreeNode:
2    # Initializer for the TreeNode class
3    def __init__(self, value=0, left=None, right=None):
4        self.value = value
5        self.left = left
6        self.right = right
7
8class Solution:
9    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
10        """
11        Trims the binary search tree such that all values are between the given low and high range (inclusive).
12        Removes nodes that are not within the range, and adjusts the tree accordingly.
13      
14        :param root: The root of the binary search tree.
15        :param low: The lower bound of the range to keep.
16        :param high: The upper bound of the range to keep.
17        :return: The root of the trimmed binary search tree.
18        """
19        # Helper function to perform the trimming using depth-first search.
20        def trim(root):
21            # If we have reached a null node, return it
22            if root is None:
23                return root
24          
25            # If the current node's value is greater than the high cutoff, move to the left subtree
26            if root.value > high:
27                return trim(root.left)
28          
29            # If the current node's value is less than the low cutoff, move to the right subtree
30            if root.value < low:
31                return trim(root.right)
32          
33            # Otherwise, the current node's value is within the range [low, high]
34            # We recursively trim the left and right subtrees
35            root.left = trim(root.left)
36            root.right = trim(root.right)
37          
38            # Return the node after potentially trimming its subtrees
39            return root
40
41        # Start the trimming process from the root
42        return trim(root)
43

Java Solution

1// Class definition for a binary tree node.
2class TreeNode {
3    int val; // Value of the node.
4    TreeNode left; // Reference to the left subtree.
5    TreeNode right; // Reference to the right subtree.
6
7    // Constructor for creating a tree node without children.
8    TreeNode() {}
9
10    // Constructor for creating a tree node with a specific value.
11    TreeNode(int val) { this.val = val; }
12  
13    // Constructor for creating a tree node with a specific value and children.
14    TreeNode(int val, TreeNode left, TreeNode right) {
15        this.val = val;
16        this.left = left;
17        this.right = right;
18    }
19}
20
21public class Solution {
22  
23    /**
24     * Trims the binary search tree (BST) so that all its elements lie between the
25     * 'low' and 'high' values, inclusive.
26     * If the node value is less than 'low', it trims the left subtree.
27     * If the node value is greater than 'high', it trims the right subtree.
28     *
29     * @param root The root of the binary search tree.
30     * @param low The lower limit of the range of values to be kept in the BST.
31     * @param high The upper limit of the range of values to be kept in the BST.
32     * @return The root of the trimmed binary search tree.
33     */
34    public TreeNode trimBST(TreeNode root, int low, int high) {
35        // Base case: if the root is null, return null since there's nothing to trim.
36        if (root == null) {
37            return null;
38        }
39      
40        // If the current node's value is greater than 'high', trim the left subtree,
41        // as none of the nodes in the right subtree can have value <= 'high'.
42        if (root.val > high) {
43            return trimBST(root.left, low, high);
44        }
45      
46        // If the current node's value is less than 'low', trim the right subtree,
47        // as none of the nodes in the left subtree can have value >= 'low'.
48        if (root.val < low) {
49            return trimBST(root.right, low, high);
50        }
51      
52        // Recursively trim the left and right subtrees.
53        root.left = trimBST(root.left, low, high);
54        root.right = trimBST(root.right, low, high);
55      
56        // Return the trimmed subtree rooted at the current node.
57        return root;
58    }
59}
60

C++ Solution

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8  
9    // Constructor with no arguments initializes value to zero and child pointers to nullptr 
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11  
12    // Constructor that initializes value with argument x and child pointers to nullptr 
13    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14
15    // Constructor that initializes the node with the given value and left and right subtree  
16    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 
17};
18
19class Solution {
20public:
21    /* Function to trim nodes of a binary search tree such that all its elements 
22     * lie in the range [low, high]. Values outside the range are removed 
23     * and the tree is modified accordingly.
24     */
25    TreeNode* trimBST(TreeNode* root, int low, int high) {
26        // If the node is null, just return null
27        if (!root) return root;
28
29        // If the node's value is greater than the high boundary, trim the right subtree
30        if (root->val > high) return trimBST(root->left, low, high);
31
32        // If the node's value is less than the low boundary, trim the left subtree
33        if (root->val < low) return trimBST(root->right, low, high);
34      
35        // Node value is within range, recursively trim the left and right subtrees
36        root->left = trimBST(root->left, low, high);
37        root->right = trimBST(root->right, low, high);
38      
39        // Return the node after trimming subtrees as it is within the [low, high] range
40        return root;
41    }
42};
43

Typescript Solution

1// Define the structure for a binary tree node.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Trims a binary search tree to contain only values in the [low, high] range.
10 * @param root - The root node of the binary search tree.
11 * @param low - The lower bound of the allowed value range.
12 * @param high - The upper bound of the allowed value range.
13 * @returns The root node of the trimmed binary search tree.
14 */
15function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
16    // Helper method that performs a depth-first search to trim the tree.
17    function depthFirstSearch(node: TreeNode | null): TreeNode | null {
18        if (node === null) {
19            return null;
20        }
21      
22        // If the current node's value is less than low, trim the left subtree.
23        if (node.val < low) {
24            return depthFirstSearch(node.right);
25        }
26        // If the current node's value is greater than high, trim the right subtree.
27        else if (node.val > high) {
28            return depthFirstSearch(node.left);
29        }
30      
31        // Otherwise, recursively trim the left and right subtrees and attach to the current node.
32        node.left = depthFirstSearch(node.left);
33        node.right = depthFirstSearch(node.right);
34        return node;
35    }
36  
37    // Kick off the depth-first search with the root node.
38    return depthFirstSearch(root);
39}
40
Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

Time Complexity

The time complexity of this function is O(n), where n is the number of nodes in the binary tree. This is because, in the worst case, each node of the tree will be visited once when the function dfs is called recursively. Even though pruning occurs for nodes that are outside the [low, high] range, the function will still visit each node to check if it meets the conditions to be included in the trimmed binary tree.

Space Complexity

The space complexity of this function is O(h), where h is the height of the binary tree. This space is used on the call stack because the function is recursive. In the best case, the binary tree is balanced and the height h would be log(n), which results in a space complexity of O(log(n)). However, in the worst case (if the tree is extremely unbalanced), the height could be n, which would result in a space complexity of O(n).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫