Delete Leaves With a Given Value: Recursive Tree Pruning

You are given a binary tree and a target integer. Remove all leaf nodes that have the given target value. After removing those leaves, some parent nodes may become new leaves with the target value. Keep removing until no such leaves remain.

This is LeetCode 1325: Delete Leaves With a Given Value. It is a clean example of recursive tree pruning where a single post-order pass handles cascading deletions without any extra loops.

Why this problem matters

Tree modification problems test whether you can think recursively about structure changes. When you remove a leaf, the tree's shape changes. A node that was not a leaf before might become one. The naive approach would be to loop, scanning and deleting leaves repeatedly until nothing changes. But there is a much better way.

The key realization is that post-order traversal naturally handles cascading. If you process children before the parent, by the time you look at a node, its subtrees are already pruned. If removing a child turned the current node into a leaf with the target value, you catch it right there in the same pass. No repeated scans, no extra loops.

The key insight

Post-order traversal processes left, right, then current. By the time you evaluate a node, both of its children have already been processed and potentially removed. If a node's only child was a target leaf that just got deleted, that node is now a leaf itself. You check it immediately, in the same recursive call. One traversal handles all cascading deletions.

The trick is to return None (or null) when a node should be deleted, and let the parent update its child pointer based on that return value.

The solution

def removeLeafNodes(root, target):
    if root is None:
        return None
    root.left = removeLeafNodes(root.left, target)
    root.right = removeLeafNodes(root.right, target)
    if root.left is None and root.right is None and root.val == target:
        return None
    return root

The function recurses into the left and right children first, reassigning the results back to root.left and root.right. This is the post-order structure: process children, then handle the current node. After both children are processed, you check whether the current node is now a leaf (both children are None) and whether its value matches the target. If so, return None to delete it. Otherwise, return the node unchanged.

The reassignment is what makes cascading work. When a child returns None, the parent's pointer updates immediately. If that makes the parent a leaf with the target value, the very next line catches it.

Visual walkthrough

Let's trace through the tree [1, 2, 3, 2, null, 2, 4] with target = 2. Watch how post-order traversal handles cascading deletions in a single pass.

Notice how we never needed a second pass. The bottom-left leaf (value 2) was removed first. Then when we checked its parent (also value 2), it had already lost its only child and became a leaf itself. The post-order structure caught it in the same recursive unwind.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node you do O(1) work: two recursive calls (which are the traversal itself) and one leaf check with a value comparison. No node is visited more than once, even though cascading deletions happen.

Space is O(h) where h is the height of the tree. This is the recursion stack depth. For a balanced tree, h = O(log n). For a completely skewed tree (like a linked list), h = O(n).

The building blocks

1. Post-order traversal for tree modification

When you need to modify a tree based on subtree results, post-order is the natural choice. Process children first, then decide what to do with the current node based on the updated children. The skeleton looks like this:

def modify(node):
    if node is None:
        return None
    node.left = modify(node.left)
    node.right = modify(node.right)
    if SHOULD_DELETE(node):
        return None
    return node

This pattern appears in any problem where removing or changing nodes depends on the state of their subtrees. The key is reassigning node.left and node.right to the return values, so deletions propagate upward.

2. Recursive tree pruning

Pruning means removing parts of a tree that do not satisfy some condition. The recursive approach returns None for nodes that should be removed and lets the parent update its pointer. This avoids the need for parent pointers or iterative deletion loops. The condition can be anything: a value check, a subtree sum check, or a structural property.

Edge cases

• Root itself is a target leaf: if the tree is a single node with the target value, the function returns None. The entire tree is deleted.
• Empty tree (root is None): the base case returns None immediately. No work to do.
• All nodes have the target value: every leaf gets deleted, which cascades upward. Eventually the root becomes a leaf with the target value and gets deleted too. The function returns None.
• No leaves match the target: the function visits every node, finds no matches, and returns the tree unchanged.
• Deep cascading chain: consider a tree that is a single path of nodes all with the target value. The bottom node is deleted, then the next one becomes a leaf and is deleted, and so on up to the root. Post-order handles this in one pass because each deletion happens during the recursive unwind.

From understanding to recall

You just traced through a solution that uses post-order traversal to prune target leaves in a single pass. You saw how reassigning child pointers after recursive calls lets cascading deletions happen automatically. It makes sense right now.

But in an interview, will you remember to recurse into children before checking the current node? Will you remember to reassign root.left and root.right to the recursive return values? Or will you write a loop that repeatedly scans for leaves, turning an O(n) solution into O(n^2)?

Understanding is not recall. You understood the solution. Recall means you can write it cold, under pressure, without forgetting the reassignment step or mixing up pre-order and post-order.

Spaced repetition builds recall. You practice writing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the base case, the recursive calls with reassignment, and the leaf check from memory. After a few repetitions, the post-order pruning pattern is automatic.

These building blocks are part of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Pruning - Similar recursive pruning pattern where you remove subtrees that do not contain a 1
• Balanced Binary Tree - Post-order tree computation that validates a property bottom-up
• Subtree of Another Tree - Recursive tree comparison using subtree structure

CodeBricks breaks problems like this into reusable building blocks and drills them with spaced repetition so you can recall patterns under pressure, not just recognize them while reading.