669. Trim a Binary Search Tree - Explanation

Problem Link



Intuition

The BST property gives us a powerful pruning strategy. If the current node's value is greater than high, then the node and its entire right subtree are too large, so we can discard them and only keep the trimmed left subtree. Similarly, if the value is less than low, the node and its left subtree are too small. When the node is within range, we recursively trim both children and attach the results.

Algorithm

  1. If the current node is null, return null (base case).
  2. If the node's value is greater than high, return the result of trimming the left subtree (discard current node and right subtree).
  3. If the node's value is less than low, return the result of trimming the right subtree (discard current node and left subtree).
  4. Otherwise, recursively trim both left and right children, attach them to the current node, and return the node.
# 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]:
        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)

        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n) for recursion stack.

2. Iterative DFS

Intuition

We can avoid recursion by using a stack. The idea remains the same: nodes outside the range need to be replaced by their valid children. We first find a valid root, then process the tree using the stack, fixing any out-of-range children by replacing them with their appropriate grandchildren.

Algorithm

  1. Find the new root by moving to the right child if the current root is too small, or to the left child if too large, until the root is within [low, high].
  2. Initialize a stack with the valid root.
  3. While the stack is not empty:
    • Pop a node.
    • If the left child exists and its value is less than low, replace it with its right child.
    • If the right child exists and its value is greater than high, replace it with its left child.
    • If any replacement was made, push the node back for reprocessing.
    • Otherwise, push both children (if they exist) onto the stack.
  4. Return the valid root.
# 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, low, high):
        while root and (root.val < low or root.val > high):
            if root.val < low:
                root = root.right
            else:
                root = root.left

        stack = [root]
        while stack:
            node = stack.pop()
            if not node:
                continue
            left_out = node.left and node.left.val < low
            right_out = node.right and node.right.val > high
            if left_out:
                node.left = node.left.right
            if right_out:
                node.right = node.right.left
            if left_out or right_out:
                stack.append(node)
            else:
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return root

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Iterative DFS (Optimal)

Intuition

Instead of using a stack, we can trim the tree in two linear passes. After finding a valid root, we traverse down the left spine fixing any nodes that fall below low, then traverse down the right spine fixing any nodes that exceed high. This works because in a BST, once we fix a node on one side, we only need to continue checking in that direction.

Algorithm

  1. Find a valid root by skipping nodes outside the range.
  2. Save the valid root as tmpRoot.
  3. Traverse the left spine: while there is a left child with value less than low, replace it with its right child. Move to the next left child.
  4. Reset to tmpRoot and traverse the right spine: while there is a right child with value greater than high, replace it with its left child. Move to the next right child.
  5. Return tmpRoot.
# 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]:
        while root and (root.val < low or root.val > high):
            root = root.right if root.val < low else root.left

        tmpRoot = root
        while root:
            while root.left and root.left.val < low:
                root.left = root.left.right
            root = root.left

        root = tmpRoot
        while root:
            while root.right and root.right.val > high:
                root.right = root.right.left
            root = root.right

        return tmpRoot

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.

Common Pitfalls

Forgetting to Recursively Trim After Skipping a Node

When a node's value is outside the range and you skip to its child, you must continue trimming that child subtree. A common mistake is to simply return the child without recursively processing it. The child itself or its descendants may also be outside the valid range and need trimming.

Confusing Which Subtree to Keep When Node is Out of Range

When a node's value is greater than high, you should return the trimmed left subtree (not the right). When a node's value is less than low, you should return the trimmed right subtree (not the left). Mixing these up violates the BST property and produces incorrect results.

Not Handling the Case Where the Root Itself is Invalid

The root node may be outside the [low, high] range, meaning the entire original root gets discarded. A common oversight is assuming the root will always be valid. Your solution must handle finding a new valid root by traversing into the appropriate subtree before beginning the main trimming logic.