Problem Description

You are given a binary search tree (BST) and two integer boundaries: low and high. Your task is to trim the tree by removing all nodes whose values fall outside the range [low, high].

The trimming process must follow these rules:

• Remove any node with a value less than low
• Remove any node with a value greater than high
• Keep all nodes with values between low and high (inclusive)
• Preserve the BST property and relative structure of the remaining nodes

For example, if a parent-child relationship exists between two nodes that both remain in the trimmed tree, that relationship must be maintained. The trimming operation may cause the root of the tree to change if the original root's value is outside the specified range.

The function should return the root of the modified tree. It's guaranteed that there is exactly one unique result for any given input.

The solution uses a depth-first search (DFS) approach that leverages the BST property:

• When a node's value is greater than high, all nodes in its right subtree will also be too large (BST property), so we only need to explore the left subtree
• When a node's value is less than low, all nodes in its left subtree will also be too small, so we only need to explore the right subtree
• When a node's value is within [low, high], we keep the node and recursively trim both its left and right subtrees

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary search tree is a special type of graph where each node has at most two children and follows specific ordering properties.

Is it a tree?

• Yes: The problem explicitly deals with a binary search tree, which is a tree data structure.

DFS

• Conclusion: Since we're working with a tree structure, the flowchart leads us directly to DFS (Depth-First Search).

The flowchart analysis confirms that DFS is the appropriate approach for this problem. This makes sense because:

1. We need to traverse the entire tree to identify nodes that fall outside the [low, high] range
2. We need to recursively process subtrees and make decisions based on node values
3. The BST property allows us to make intelligent pruning decisions - if a node's value is too high, we know its entire right subtree can be discarded
4. DFS naturally handles the recursive nature of trimming subtrees and reconnecting valid nodes

The DFS approach efficiently explores the tree depth-first, making trimming decisions at each node based on its value relative to the boundaries, and recursively processing child nodes to build the trimmed tree from the bottom up.

Intuition

The key insight comes from understanding the binary search tree property: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger.

When we encounter a node during traversal, we can make smart decisions based on its value:

1. If node.val > high: This node is too large and must be removed. But here's the crucial observation - since this is a BST, every node in the right subtree will also be greater than high. So we can completely ignore the right subtree and only look at the left subtree for potential valid nodes.

2. If node.val < low: This node is too small and must be removed. Similarly, every node in the left subtree will also be less than low. So we can completely ignore the left subtree and only look at the right subtree.

3. If low <= node.val <= high: This node is valid and should be kept. However, both subtrees might contain invalid nodes, so we need to recursively trim both children.

The beauty of this approach is that we're not just blindly checking every node - we're using the BST structure to eliminate entire subtrees when possible. When a node is out of bounds, we effectively "skip over" it by returning the result of trimming the appropriate subtree, which naturally maintains the BST property.

For example, if we have a node with value 15 and our high limit is 10, we know that this node and everything to its right (values > 15) are invalid. The trimmed tree for this subtree would be whatever valid nodes exist in the left subtree.

This recursive approach naturally handles the restructuring of the tree - when we return a different node than the current one (because it was out of bounds), we're effectively promoting a descendant to take its place, maintaining all the parent-child relationships that should exist in the final trimmed tree.

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

Solution Approach

The implementation uses a recursive DFS function to traverse and trim the tree. Let's walk through the solution step by step:

Base Case:

if root is None:
    return root

If we reach a null node, we simply return None. This handles leaf nodes and empty subtrees.

Case 1: Node value exceeds the upper bound

if root.val > high:
    return dfs(root.left)

When the current node's value is greater than high, we know:

• This node must be removed
• All nodes in the right subtree will also be > high (BST property)
• Only the left subtree might contain valid nodes

So we discard the current node and its right subtree entirely, returning whatever valid tree we can build from the left subtree.

Case 2: Node value is below the lower bound

if root.val < low:
    return dfs(root.right)

When the current node's value is less than low, we know:

• This node must be removed
• All nodes in the left subtree will also be < low (BST property)
• Only the right subtree might contain valid nodes

We discard the current node and its left subtree, returning the trimmed version of the right subtree.

Case 3: Node value is within bounds

root.left = dfs(root.left)
root.right = dfs(root.right)
return root

When low <= root.val <= high, the current node is valid and should be kept. However, both subtrees might still contain invalid nodes, so we:

• Recursively trim the left subtree and update the left child pointer
• Recursively trim the right subtree and update the right child pointer
• Return the current node as the root of this trimmed subtree

The Recursion Flow: The function works bottom-up, trimming subtrees first before deciding what to do with parent nodes. This ensures that when we update a node's children, we're pointing to already-trimmed subtrees.

For example, with low=3, high=8 and a node with value 5:

1. Recursively trim left subtree (values < 5)
2. Recursively trim right subtree (values > 5)
3. Update this node's children to point to the trimmed subtrees
4. Return this node as it's within bounds

The elegance of this solution lies in how it leverages the BST property to avoid unnecessary traversals while maintaining the tree structure for all valid nodes.

Example Walkthrough

Let's walk through trimming a BST with low = 3 and high = 8:

Initial Tree:        After Trimming:
      5                    5
     / \                  / \
    2   7                3   7
   / \   \                    \
  1   3   9                    8
           \
            10

Step-by-step process:

1. Start at root (5): Value 5 is within [3, 8], so we keep it and recursively trim both subtrees.

2. Process left subtree (node 2): Value 2 < 3, so this node must be removed. Since all values in its left subtree (node 1) will also be < 3, we ignore the left and only consider the right subtree. We return dfs(node 3).

3. Process node 3: Value 3 is within [3, 8], so we keep it. It has no children, so we return node 3. This becomes the new left child of node 5.

4. Process right subtree (node 7): Value 7 is within [3, 8], so we keep it and recursively trim both subtrees.

5. Process node 7's right child (node 9): Value 9 > 8, so this node must be removed. Since all values in its right subtree (node 10) will also be > 8, we ignore the right and only consider the left subtree. Since node 9 has no left child, we return None.

6. Back to node 7: We update its right child to None and return node 7.

7. Back to root (5): We've now trimmed both subtrees. The left child is updated to node 3, and the right child remains node 7. We return node 5 as the root.

Wait, let me reconsider the example with a tree that better demonstrates the algorithm:

Initial Tree:        After Trimming:
      6                    6
     / \                  / \
    3   10               4   8
   / \  / \               \
  1   4 8  12              5
       \
        5

Step-by-step process with low = 4, high = 8:

1. Start at root (6): Value 6 is within [4, 8], keep it and recursively trim both subtrees.

2. Left subtree (node 3): Value 3 < 4, so remove this node. Ignore left subtree (node 1) and return dfs(node 4).

3. Process node 4: Value 4 is within [4, 8], keep it. Recursively trim its right child (node 5).

4. Process node 5: Value 5 is within [4, 8], keep it. No children, return node 5.

5. Back to node 4: Right child stays as node 5, return node 4. This becomes the new left child of root.

6. Right subtree (node 10): Value 10 > 8, so remove this node. Ignore right subtree (node 12) and return dfs(node 8).

7. Process node 8: Value 8 is within [4, 8], keep it. No children, return node 8. This becomes the new right child of root.

8. Final result: Root node 6 with left child 4 (which has right child 5) and right child 8.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary search tree. In the worst case, we need to visit every node in the tree exactly once. Even though we might skip entire subtrees when a node's value is outside the [low, high] range, each node is still processed at most once during the traversal.

Space Complexity: O(h) where h is the height of the tree. This space is used by the recursive call stack. In the worst case of a completely unbalanced tree (essentially a linked list), the height could be O(n), making the space complexity O(n). In the best case of a perfectly balanced tree, the height would be O(log n), making the space complexity O(log n).

The algorithm performs a depth-first search traversal where:

• If a node's value is greater than high, we trim the node and its entire right subtree, recursing only on the left subtree
• If a node's value is less than low, we trim the node and its entire left subtree, recursing only on the right subtree
• If a node's value is within [low, high], we keep the node and recursively trim both its left and right subtrees

The algorithm leverages the BST property to efficiently prune entire subtrees without examining all their nodes, but the complexity analysis considers the worst case where we might need to examine all nodes.

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

Common Pitfalls

Pitfall 1: Incorrectly Trying to Preserve Parent-Child Links

A common mistake is attempting to manually reconnect nodes after deletion, rather than letting the recursion handle the restructuring naturally.

Incorrect Approach:

def trimBST(self, root, low, high):
    if not root:
        return None
  
    # WRONG: Trying to manually handle parent connections
    if root.val < low:
        # Attempting to find a valid node and reconnect
        right_child = root.right
        while right_child and right_child.val < low:
            right_child = right_child.right
        if right_child:
            right_child.left = root.left  # This breaks BST property!
        return self.trimBST(right_child, low, high)

Why it's wrong: This approach tries to manually reconnect nodes, which can violate the BST property and miss nodes that should be included.

Correct Solution: Let recursion handle the connections naturally:

if root.val < low:
    # Simply return the trimmed right subtree
    return self.trimBST(root.right, low, high)

Pitfall 2: Using In-Order Traversal to Collect and Rebuild

Some might think to traverse the tree, collect valid nodes, and rebuild a new BST.

Inefficient Approach:

def trimBST(self, root, low, high):
    # Collect all valid values
    valid_values = []
  
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        if low <= node.val <= high:
            valid_values.append(node.val)
        inorder(node.right)
  
    inorder(root)
  
    # Rebuild BST from valid values
    def build_bst(values):
        # Complex rebuilding logic...
        pass
  
    return build_bst(valid_values)

Why it's wrong: This approach has several issues:

• Time complexity becomes O(n log n) for rebuilding instead of O(n)
• Space complexity increases to O(n) for storing values
• The original tree structure is lost unnecessarily
• More complex implementation

Correct Solution: Modify the tree in-place during traversal, maintaining the original structure where possible.

Pitfall 3: Forgetting to Update Child Pointers

A subtle but critical mistake is traversing without updating the parent's child pointers.

Incorrect Approach:

def trimBST(self, root, low, high):
    if not root:
        return None
  
    if root.val > high:
        return self.trimBST(root.left, low, high)
  
    if root.val < low:
        return self.trimBST(root.right, low, high)
  
    # WRONG: Just calling recursion without updating pointers
    self.trimBST(root.left, low, high)
    self.trimBST(root.right, low, high)
  
    return root

Why it's wrong: This traverses the tree but doesn't actually remove any nodes because the child pointers are never updated to reflect the trimmed subtrees.

Correct Solution: Always assign the recursive results back to the child pointers:

# Update the pointers to trimmed subtrees
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root

Pitfall 4: Misunderstanding When to Explore Subtrees

Some solutions incorrectly explore both subtrees even when one can be completely discarded.

Incorrect Approach:

def trimBST(self, root, low, high):
    if not root:
        return None
  
    # WRONG: Always exploring both subtrees
    root.left = self.trimBST(root.left, low, high)
    root.right = self.trimBST(root.right, low, high)
  
    # Then checking if current node should be removed
    if root.val < low or root.val > high:
        if root.val < low:
            return root.right
        else:
            return root.left
  
    return root

Why it's wrong: This explores unnecessary subtrees. When root.val > high, we know the entire right subtree is invalid (BST property), so exploring it wastes time.

Correct Solution: Check the current node's value first and only explore relevant subtrees based on BST properties.