LeetCode 669: Trim a Binary Search Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 669: Trim a Binary Search Tree?

In LeetCode 669: Trim a Binary Search Tree, you’re given the root of a binary search tree (BST) and two integers low and high. Your task is to trim the tree so that all remaining node values lie within the inclusive range [low, high], preserving the BST property (left subtree < node < right subtree). Return the root of the trimmed tree. For example, with root = [3, 0, 4, null, 2, null, null, 1] and range [1, 3], you’d remove 0 (too low) and 4 (too high), resulting in [3, 2, null, 1]. This problem tests your ability to manipulate a BST while maintaining its structure.

Problem Statement

• Input:
• root: Root node of a BST.
• low: Integer (lower bound, inclusive).
• high: Integer (upper bound, inclusive).
• Output: Root node of the trimmed BST.
• Rules:
• Keep nodes with values in [low, high].
• Remove nodes outside this range, including subtrees.
• Preserve BST property.

Constraints

• Number of nodes: 1 to 10⁴.
• 0 ≤ Node.val ≤ 10⁴.
• 0 ≤ low ≤ high ≤ 10⁴.
• Input is a valid BST.

Examples

• Input: root = [1, 0, 2], low = 1, high = 2
• Output: [1, null, 2] (Remove 0)
• Input: root = [3, 0, 4, null, 2, null, null, 1], low = 1, high = 3
• Output: [3, 2, null, 1] (Remove 0, 4)
• Input: root = [1], low = 1, high = 2
• Output: [1] (No trimming needed)

These examples set the tree—let’s solve it!

Understanding the Problem: Trimming the BST

To solve LeetCode 669: Trim a Binary Search Tree in Python, we need to trim a BST to keep only nodes with values in [low, high], preserving the BST property. A brute-force approach—traversing and rebuilding—would work but could be inefficient. Since it’s a BST, we can leverage its ordering (left < node < right) to prune recursively or iteratively. We’ll use:

• Best Solution (Recursive Trimming): O(n) time, O(h) space—fast and elegant (h = height).
• Alternative Solution (Iterative with Stack): O(n) time, O(n) space—manual but explicit.

Let’s start with the recursive solution, breaking it down for beginners.

Best Solution: Recursive Trimming

Why This Is the Best Solution

The recursive trimming approach is the top choice for LeetCode 669 because it’s efficient—O(n) time with O(h) space—and elegantly uses the BST property to prune subtrees recursively, naturally maintaining the structure without extra bookkeeping. It fits constraints (n ≤ 10⁴) perfectly and is intuitive once you see the recursion. It’s like pruning the tree branch-by-branch with a smart rulebook!

How It Works

Think of this as a tree trimmer:

• Step 1: Base Case:
• If node is None, return None.
• Step 2: Trim Low Values:
• If node.val < low:
• Discard node and left subtree (all < low).
• Recurse on right subtree.
• Step 3: Trim High Values:
• If node.val > high:
• Discard node and right subtree (all > high).
• Recurse on left subtree.
• Step 4: Keep Node:
• If low ≤ node.val ≤ high:
• Recurse on left and right children.
• Return trimmed node.
• Step 5: Return Result:
• Return root of trimmed tree.

It’s like a BST pruner—cut and keep!

Step-by-Step Example

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

• Step 1: Start at root (3):
• 1 ≤ 3 ≤ 3, keep 3, recurse on children.
• Step 2: Left child (0):
• 0 < 1, discard 0 and its left (none), recurse on right (2).
• Step 3: Right child of 0 (2):
• 1 ≤ 2 ≤ 3, keep 2, recurse on children.
• Left (1): 1 ≤ 1 ≤ 3, keep 1, no children, return 1.
• Right (null): Return null.
• 2.left = 1, 2.right = null, return 2.
• Step 4: Right child of 3 (4):
• 4 > 3, discard 4 and its right (none), recurse on left (null), return null.
• Step 5: Root 3:
• 3.left = 2, 3.right = null, return [3, 2, null, 1].
• Output: [3, 2, null, 1].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass 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: TreeNode, low: int, high: int) -> TreeNode:
        # Step 1: Base case
        if not root:
            return None

        # Step 2: Trim low values
        if root.val < low:
            # Discard node and left subtree, recurse on right
            return self.trimBST(root.right, low, high)

        # Step 3: Trim high values
        if root.val > high:
            # Discard node and right subtree, recurse on left
            return self.trimBST(root.left, low, high)

        # Step 4: Keep node, recurse on children
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

• Lines 1-6: TreeNode class (standard).
• Lines 10-11: Base case: Null node returns null.
• Lines 14-16: Trim low: Discard if < low, recurse right.
• Lines 19-21: Trim high: Discard if > high, recurse left.
• Lines 24-26: Keep: Trim children, return node.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h = height).

This is like a tree sculptor—prune and shape!

Alternative Solution: Iterative with Stack

Why an Alternative Approach?

The iterative with stack approach uses a stack to traverse—O(n) time, O(n) space. It’s more manual, explicitly handling parent pointers, but offers insight into iterative tree manipulation. It’s like pruning the tree step-by-step with a checklist!

How It Works

Picture this as a tree checker:

• Step 1: Use stack to traverse preorder.
• Step 2: Track parents, adjust pointers:
• If node < low, skip to right child.
• If node > high, skip to left child.
• Step 3: Rebuild structure iteratively.
• Step 4: Return trimmed root.

It’s like a manual pruner—stack and adjust!

Step-by-Step Example

Example: Same as above

• Step 1: Stack = [(None, 3)], root = 3.
• Step 2: Process:
• Pop (None, 3): 1 ≤ 3 ≤ 3, push (3, 0), (3, 4).
• Pop (3, 4): 4 > 3, 3.right = null, push (4, null).
• Pop (4, null): Skip.
• Pop (3, 0): 0 < 1, 3.left = 2, push (0, 2).
• Pop (0, 2): 1 ≤ 2 ≤ 3, push (2, 1), (2, null).
• Pop (2, null): Skip.
• Pop (2, 1): 1 ≤ 1 ≤ 3, 2.left = 1.
• Step 3: Root = [3, 2, null, 1].
• Output: [3, 2, null, 1].

Code for Iterative Approach

Copy codeclass Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None

        # Step 1: Initialize stack with (parent, node)
        stack = [(None, root)]
        new_root = root

        # Step 2: Iterative traversal
        while stack:
            parent, node = stack.pop()

            # Trim low values
            while node and node.val < low:
                if parent:
                    parent.left = node.right
                else:
                    new_root = node.right
                node = node.right

            # Trim high values
            while node and node.val > high:
                if parent:
                    parent.right = node.left
                else:
                    new_root = node.left
                node = node.left

            # Process children
            if node:
                if node.right:
                    stack.append((node, node.right))
                if node.left:
                    stack.append((node, node.left))

        # Step 3: Return trimmed root
        return new_root

• Lines 4-8: Init: Stack with root, track new root.
• Lines 11-32: Traverse:
• Trim low/high, adjust parent pointers, push children.
• Line 35: Return new_root.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(n)—stack size.

It’s a stack trimmer—iterate and fix!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(n) time, O(h) space, elegant and concise.
• Cons: Recursion stack for deep trees.
• Iterative (Alternative):
• Pros: O(n) time, O(n) space, explicit control.
• Cons: More complex pointer management.

Recursive wins for simplicity.

Additional Examples and Edge Cases

• Input: [1], low = 1, high = 1
• Output: [1].
• Input: [2, 1, 3], low = 3, high = 4
• Output: [3] (Trim 1, 2).

Recursive handles these well.

Complexity Breakdown

• Recursive: Time O(n), Space O(h).
• Iterative: Time O(n), Space O(n).

Recursive is optimal for space.

Key Takeaways

• Recursive: Elegant pruning—smart!
• Iterative: Stack control—clear!
• Trimming: Trees are fun.
• Python Tip: Recursion rocks—see Python Basics.

Final Thoughts: Trim That Tree

LeetCode 669: Trim a Binary Search Tree in Python is a fun tree challenge. Recursive trimming offers simplicity and efficiency, while iterative with stack provides a hands-on alternative. Want more? Try LeetCode 98: Validate Binary Search Tree or LeetCode 108: Convert Sorted Array to BST. Ready to prune? Head to Solve LeetCode 669 on LeetCode and trim that BST today!