Trim a BST

▶

Steps

setup

Initialize root and parameters

The initial BST is constructed with root value 3, and the range [1,3] is set. No pruning has started yet.

💡 Setting up the tree and range is essential before pruning begins.

Line:

root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
low, high = 1, 3

💡 The tree structure and range are now ready for trimming.

setup

Move root down because root.val (3) is within [1,3]

Check if root.val is outside the range. Since 3 is within [1,3], root remains at node 3.

💡 The root must be within range to start trimming subtrees.

Line:

while root and (root.val < low or root.val > high):
    if root.val < low:
        root = root.right
    elif root.val > high:
        root = root.left

💡 Root is valid; pruning will proceed on subtrees.

fill_row

Start trimming left subtree from root (node 3)

Set current pointer 'cur' to root to begin trimming the left subtree.

💡 We will iteratively check left children to remove nodes less than low.

Line:

cur = root

💡 Starting point for left subtree pruning is root.

fill_cells

Check left child of node 3 (node 0) for pruning

Node 3's left child is node 0, which has value less than low (1). We will prune node 0 by moving left pointer to node 0's right child (node 2).

💡 Nodes less than low must be removed from the left subtree.

Line:

while cur.left and cur.left.val < low:
    cur.left = cur.left.right

💡 Pruning node 0 removes invalid left subtree nodes efficiently.

fill_cells

Move cur pointer down to left child (node 2) to continue left subtree trimming

After pruning node 0, move cur to its left child node 2 to check if further pruning is needed.

💡 We must check all left descendants for nodes less than low.

Line:

cur = cur.left

💡 Traversal continues down left subtree to prune all invalid nodes.

fill_cells

Check left child of node 2 (node 1) for pruning

Node 2's left child is node 1, which is within the range [1,3], so no pruning is needed here.

💡 Nodes within range remain untouched.

Line:

while cur.left and cur.left.val < low:
    cur.left = cur.left.right

💡 Pruning stops when left child is valid.

fill_cells

Move cur pointer down to left child (node 1) to continue left subtree trimming

Move cur to node 1 to check if it has left children needing pruning.

💡 We continue down the left subtree to ensure all nodes are valid.

Line:

cur = cur.left

💡 Traversal continues to leaf nodes for pruning checks.

fill_row

Left subtree trimming complete, start trimming right subtree from root (node 3)

Set cur pointer back to root to begin trimming the right subtree.

💡 Now we will remove nodes greater than high from the right subtree.

Line:

cur = root

💡 Right subtree pruning starts fresh from root.

fill_cells

Check right child of node 3 (node 2) for pruning

Node 3's right child is node 2, which has value greater than high (3). We prune node 2 by moving right pointer to node 2's left child (node 4).

💡 Nodes greater than high must be removed from the right subtree.

Line:

while cur.right and cur.right.val > high:
    cur.right = cur.right.left

💡 Pruning node 2 removes invalid right subtree nodes efficiently.

fill_cells

Move cur pointer down to right child (node 4) to continue right subtree trimming

Move cur to its right child node 4 to check if further pruning is needed.

💡 We continue down the right subtree to ensure all nodes are valid.

Line:

cur = cur.right

💡 Traversal continues to leaf nodes for pruning checks.

reconstruct

Return the trimmed root

The root node 3 now points to a left subtree rooted at node 2 (which has left child 1) and no right subtree. This is the trimmed BST.

💡 Returning the root completes the trimming process.

Line:

return root

💡 The final tree contains only nodes within [1,3].

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def trimBST(root, low, high):
    # STEP 2: Move root to valid range
    while root and (root.val < low or root.val > high):
        if root.val < low:
            root = root.right  # STEP 2: root moves right
        elif root.val > high:
            root = root.left   # STEP 2: root moves left
    if not root:
        return None
    # STEP 3: Trim left subtree
    cur = root  # STEP 3
    while cur:
        while cur.left and cur.left.val < low:
            cur.left = cur.left.right  # STEP 4: prune left child
        cur = cur.left  # STEP 5: move cur down left
    # STEP 8: Trim right subtree
    cur = root  # STEP 8
    while cur:
        while cur.right and cur.right.val > high:
            cur.right = cur.right.left  # STEP 9: prune right child
        cur = cur.right  # STEP 10: move cur down right
    return root  # STEP 11

if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(0)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(1)
    low, high = 1, 3
    trimmed = trimBST(root, low, high)
    def print_inorder(node):
        if not node:
            return
        print_inorder(node.left)
        print(node.val, end=' ')
        print_inorder(node.right)
    print_inorder(trimmed)

📊

Trim a BST - Watch the Algorithm Execute, Step by Step

Watching each pointer move and subtree adjustment helps you understand how BST properties enable efficient pruning without recursion.

Current node: 0

30421

Current node: 0

30421

Current node: 0

30421

DFS Stack

0 (entered)cur=0

Current node: 0

30421

DFS Stack

0 (left_done)cur=0

Current node: 3

30421

DFS Stack

0 (left_done)cur=3

Current node: 3

30421

DFS Stack

0 (left_done)cur=3

Current node: 4

30421

DFS Stack

0 (left_done)cur=4

Current node: 0

30421

DFS Stack

0 (right_entered)cur=0

Current node: 0

30421

DFS Stack

0 (right_done)cur=0

Current node: 4

30421

DFS Stack

0 (right_done)cur=4

Current node: 0

32104

Return: 0

Key Takeaways

✓ The root is first moved to a valid node within the range before any pruning.

This step ensures the trimmed tree's root is always valid, which is not obvious from code alone.

✓ Left subtree pruning removes nodes less than low by adjusting left pointers iteratively.

Seeing pointer updates visually clarifies how pruning avoids recursion and preserves BST structure.

✓ Right subtree pruning removes nodes greater than high similarly by adjusting right pointers.

The symmetry of left and right pruning is easier to grasp when watching each pointer move.