Tree Pruning and Deletion Patterns

Pruning and deletion are the “destructive” operations on trees — they remove nodes or entire subtrees based on some condition. These operations appear constantly in interviews because they test your ability to think recursively about tree structure while carefully managing parent-child relationships.

This article covers the five most important pruning/deletion patterns you’ll encounter.

---

TreeNode Definition

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

---

Pattern 1: Delete a Node in BST

LeetCode 450. Given a BST and a key, delete the node with that key and return the modified root.

The tricky part is handling three cases after you find the node:

1. Leaf node — just remove it
2. One child — replace the node with its child
3. Two children — replace the node’s value with its inorder successor (smallest node in right subtree), then delete the successor

def delete_node(root, key):
    """Delete a node with the given key from BST."""
    if not root:
        return None

    if key < root.val:
        # Key is in the left subtree
        root.left = delete_node(root.left, key)
    elif key > root.val:
        # Key is in the right subtree
        root.right = delete_node(root.right, key)
    else:
        # Found the node to delete

        # Case 1 & 2: Node has 0 or 1 child
        if not root.left:
            return root.right
        if not root.right:
            return root.left

        # Case 3: Node has two children
        # Find inorder successor (smallest in right subtree)
        successor = root.right
        while successor.left:
            successor = successor.left

        # Replace current node's value with successor's value
        root.val = successor.val

        # Delete the successor from right subtree
        root.right = delete_node(root.right, successor.val)

    return root

Step-by-step example

Delete 3 from:
        5
       / \
      3   6
     / \   \
    2   4   7

Node 3 has two children.
Inorder successor of 3 is 4 (smallest in right subtree).
Replace 3 with 4, then delete 4 from right subtree.

Result:
        5
       / \
      4   6
     /     \
    2       7

Alternative: Using inorder predecessor

You can also use the inorder predecessor (largest in left subtree) instead of successor:

def delete_node_pred(root, key):
    """Delete using inorder predecessor instead of successor."""
    if not root:
        return None

    if key < root.val:
        root.left = delete_node_pred(root.left, key)
    elif key > root.val:
        root.right = delete_node_pred(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left

        # Find inorder predecessor (largest in left subtree)
        predecessor = root.left
        while predecessor.right:
            predecessor = predecessor.right

        root.val = predecessor.val
        root.left = delete_node_pred(root.left, predecessor.val)

    return root

Complexity

Metric	Value
Time	O(h) — where h is tree height
Space	O(h) — recursion stack

For a balanced BST, h = O(log n). For a skewed tree, h = O(n).

---

Pattern 2: Binary Tree Pruning (LeetCode 814)

Given a binary tree where every node’s value is either 0 or 1, prune the tree so that every subtree containing no 1s is removed.

Input:            Output:
      1                1
       \                \
        0                0
       / \                \
      0   1                1

The key insight: a subtree should be pruned if all its values are 0. We use post-order traversal — process children first, then decide about the current node.

def prune_tree(root):
    """Remove all subtrees that don't contain a 1."""
    if not root:
        return None

    # Post-order: prune children first
    root.left = prune_tree(root.left)
    root.right = prune_tree(root.right)

    # If current node is 0 and both children are pruned, prune this node
    if root.val == 0 and not root.left and not root.right:
        return None

    return root

Why post-order?

Post-order ensures we prune from the bottom up. A node with value 0 might still have a descendant with value 1, so we can’t decide to prune until we’ve resolved its children.

Complexity

Metric	Value
Time	O(n) — visit every node once
Space	O(h) — recursion stack

---

Pattern 3: Trim BST to Range

LeetCode 669. Given a BST and a range [low, high], trim the tree so that all node values lie within the range. The tree should remain a valid BST.

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

        3
       / \
      0   4
       \
        2
       /
      1

Output:
        3
       /
      2
     /
    1

Nodes 0 and 4 are outside [1, 3], so they’re removed.

def trim_bst(root, low, high):
    """Trim BST to only contain values in [low, high]."""
    if not root:
        return None

    # If current value is too small, only search right
    if root.val < low:
        return trim_bst(root.right, low, high)

    # If current value is too large, only search left
    if root.val > high:
        return trim_bst(root.left, low, high)

    # Current value is in range — trim both subtrees
    root.left = trim_bst(root.left, low, high)
    root.right = trim_bst(root.right, low, high)

    return root

The clever part

When root.val {'<'} low, we don’t just delete the current node — we skip the entire left subtree too (because all values there are even smaller). We only need to search the right subtree for valid nodes.

Complexity

Metric	Value
Time	O(n) — worst case visits every node
Space	O(h) — recursion stack

---

Pattern 4: Delete Leaves with a Given Value

LeetCode 1325. Given a binary tree and a target value, repeatedly delete all leaf nodes with the target value. After removing leaves, some internal nodes may become new leaves — if they have the target value, delete them too.

Input: target = 2
        1
       / \
      2   3
     /   / \
    2   2   4

After first pass: remove leaf 2s
        1
       / \
      2   3
           \
            4

Node 2 is now a leaf! Remove it:
        1
         \
          3
           \
            4

def remove_leaves(root, target):
    """Remove all leaves with the given target value, repeatedly."""
    if not root:
        return None

    # Post-order: process children first
    root.left = remove_leaves(root.left, target)
    root.right = remove_leaves(root.right, target)

    # If this is now a leaf with target value, prune it
    if not root.left and not root.right and root.val == target:
        return None

    return root

Why a single pass works

Because we use post-order, children are processed before parents. By the time we check the current node, its children have already been pruned. So if a node becomes a leaf after its children are removed, we catch it in the same pass.

Complexity

Metric	Value
Time	O(n)
Space	O(h)

---

Pattern 5: Delete Nodes and Return Forest

LeetCode 1110. Given a binary tree and a list of values to delete, remove those nodes and return the resulting forest (list of disjoint trees).

Input: to_delete = [3, 5]
        1
       / \
      2   3
     / \   \
    4   5   6

Output: Three trees:
    1        4      6
   /
  2

When a node is deleted, its children become roots of new trees.

def del_nodes(root, to_delete):
    """Delete nodes and return the forest."""
    to_delete_set = set(to_delete)
    forest = []

    def dfs(node, is_root):
        if not node:
            return None

        # Should this node be deleted?
        deleted = node.val in to_delete_set

        # If this is a root and it's not deleted, add to forest
        if is_root and not deleted:
            forest.append(node)

        # Children become roots if current node is deleted
        node.left = dfs(node.left, deleted)
        node.right = dfs(node.right, deleted)

        # Return None if deleted, otherwise return the node
        return None if deleted else node

    dfs(root, True)
    return forest

Complexity

Metric	Value
Time	O(n)
Space	O(n) — for the delete set and forest list

---

The Post-Order Pattern

Notice a recurring theme: pruning almost always uses post-order traversal. Here’s why:

Pre-order:  Process root → then children
            Problem: you don't know if children need the root yet

In-order:   Process left → root → right
            Problem: right subtree hasn't been processed when you decide about root

Post-order: Process children → then root
            Perfect: children are resolved, you have full information to decide

The general template for pruning:

def prune(node, condition):
    """Generic pruning template."""
    if not node:
        return None

    # Process children first (post-order)
    node.left = prune(node.left, condition)
    node.right = prune(node.right, condition)

    # Decide about current node
    if should_remove(node, condition):
        return None

    return node

---

Iterative BST Deletion

For completeness, here’s an iterative version of BST node deletion:

def delete_node_iterative(root, key):
    """Delete a node from BST iteratively."""
    # Find the node and its parent
    parent = None
    current = root

    while current and current.val != key:
        parent = current
        if key < current.val:
            current = current.left
        else:
            current = current.right

    if not current:
        return root  # Key not found

    # Case: two children
    if current.left and current.right:
        # Find inorder successor and its parent
        succ_parent = current
        successor = current.right
        while successor.left:
            succ_parent = successor
            successor = successor.left

        current.val = successor.val

        # Now delete successor (which has at most one child)
        parent = succ_parent
        current = successor

    # Case: 0 or 1 child
    child = current.left if current.left else current.right

    if not parent:
        return child  # Deleting root

    if parent.left == current:
        parent.left = child
    else:
        parent.right = child

    return root

---

Common Mistakes

1. Forgetting to reassign the child — prune(node.left) alone does nothing. You must write node.left = prune(node.left) to actually disconnect the pruned subtree.

2. Using pre-order for pruning — this can lead to incorrect results because you haven’t processed children yet. Always use post-order for bottom-up pruning.

3. Not handling the root being deleted — in BST deletion, if the root itself is the key, you need to handle the case where parent is None.

4. Confusing trim with delete — trimming a BST means removing out-of-range nodes, which may require skipping entire subtrees, not just deleting single nodes.

---

Practice Problems

Problem	Platform	Difficulty
Delete Node in a BST	LeetCode 450	Medium
Binary Tree Pruning	LeetCode 814	Medium
Trim a Binary Search Tree	LeetCode 669	Medium
Delete Leaves With a Given Value	LeetCode 1325	Medium
Delete Nodes And Return Forest	LeetCode 1110	Medium
Smallest Subtree with all the Deepest Nodes	LeetCode 865	Medium

---

Key Takeaways

• BST deletion has three cases: leaf, one child, two children. The two-children case uses the inorder successor (or predecessor).
• Pruning uses post-order — always process children before deciding about the current node.
• The pattern node.left = prune(node.left) is the standard way to disconnect pruned subtrees.
• Trim BST cleverly skips entire subtrees by leveraging the BST ordering property.
• Delete and return forest (LeetCode 1110) combines pruning with tracking — deleted nodes’ children become new roots.
• All these operations run in O(n) time — you can’t do better since you may need to visit every node.