Binary Tree Pruning: Post-Order Subtree Removal

You are given the root of a binary tree where every node's value is either 0 or 1. Return the same tree, but with every subtree that does not contain a 1 removed. A subtree of a node is that node plus all of its descendants.

This is LeetCode 814: Binary Tree Pruning. The key insight is that you need to process children before parents. If you try to decide whether to prune a node before you know whether its children survived, you will make the wrong call. Post-order traversal handles this naturally.

Why this problem matters

Binary Tree Pruning is a clean exercise in bottom-up tree transformation. Unlike problems that only read the tree, this one modifies it. You are not just returning a boolean or an integer. You are returning a new tree structure with entire branches removed.

The problem teaches you to think about recursive return values as signals. When a recursive call returns None, it means "this entire subtree is gone." When it returns a node, it means "this subtree has at least one 1 and should stay." That return-value-as-signal pattern shows up in many tree problems, from Balanced Binary Tree (returning -1 to signal imbalance) to deleting nodes in BSTs.

If you have solved Subtree of Another Tree, you are already comfortable reasoning about subtrees as self-contained units. Pruning takes that idea one step further: instead of checking a property, you are actually removing the subtrees that fail the check.

The approach

Post-order traversal means you visit the left child, then the right child, then process the current node. This guarantees that by the time you look at a node, both of its subtrees have already been pruned. Here is the logic:

1. Recursively prune the left subtree. Assign the result back to node.left.
2. Recursively prune the right subtree. Assign the result back to node.right.
3. Now check: if the current node's value is 0 and both node.left and node.right are None, this node's entire subtree contains no 1s. Return None to prune it.
4. Otherwise, return the node. It either has value 1 itself, or one of its children survived pruning, meaning a 1 exists somewhere below.

The solution

def prune_tree(root):
    if root is None:
        return None
    root.left = prune_tree(root.left)
    root.right = prune_tree(root.right)
    if root.val == 0 and root.left is None and root.right is None:
        return None
    return root

Let's walk through each piece:

• if root is None: return None is the base case. A null node stays null. There is nothing to prune.
• root.left = prune_tree(root.left) recursively prunes the left subtree and reassigns the result. If the entire left subtree contained no 1s, this sets root.left to None.
• root.right = prune_tree(root.right) does the same for the right subtree.
• The if check on the next line is the pruning decision. After both children have been processed, if this node is 0 and has no surviving children, it means the entire subtree rooted here contains no 1s. Return None to remove it from the tree.
• return root keeps the node in the tree. Either the node itself is 1, or at least one child survived, which means a 1 exists somewhere in this subtree.

Visual walkthrough

Let's trace the pruning through the tree [1, 0, 0, 0, 0, 0, 1] step by step. Watch how post-order traversal processes leaves first, then works its way up, pruning zero-only subtrees along the way.

The critical observation is that node 0 (right child of root) survives even though its own value is 0. It stays because its right child is 1. A node does not need to be 1 itself to survive. It just needs at least one 1 somewhere in its subtree.

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 counted separately) and one comparison.

Space is O(h) where h is the height of the tree. That is the depth of the recursion stack. For a balanced tree, h = log n. For a skewed tree (all nodes in a line), h = n.

The building blocks

This problem is built on two fundamental building blocks:

1. Post-order tree transformation (post-order-transform). When you need to modify a tree based on subtree properties, process children first, then decide what to do with the parent. The skeleton looks like this:

def transform(node):
    if node is None:
        return None
    node.left = transform(node.left)
    node.right = transform(node.right)
    if SHOULD_REMOVE(node):
        return None
    return node

For Binary Tree Pruning, SHOULD_REMOVE checks node.val == 0 and node.left is None and node.right is None. This same pattern applies whenever you need to remove subtrees based on some condition that depends on descendant information.

2. Return value as signal (return-value-signal). The return value of the recursive function does double duty. It both provides the pruned subtree to the parent and signals whether the subtree should exist at all. Returning None means "remove me." Returning the node means "keep me." The parent uses this signal directly by assigning it to node.left or node.right. No extra boolean flags, no global state.

Edge cases to watch for

• Empty tree (root is None): return None. The base case handles this directly.
• Single node with value 1: return the node as-is. The pruning condition checks val == 0, which is false, so the node survives.
• Single node with value 0: return None. The node is 0, has no children, so the entire tree is pruned away.
• All nodes are 1: no pruning happens. Every node has value 1, so the condition val == 0 is never true. The tree is returned unchanged.
• All nodes are 0: the entire tree is pruned. Every leaf gets removed first, then their parents become leaves with value 0 and get removed, cascading up until the root itself is removed.

From understanding to recall

You just read through a solution that uses post-order traversal to prune subtrees bottom-up. You saw how returning None signals removal and how a node with value 0 can survive if it has a descendant with value 1. The logic is compact and clean.

But will you remember, under pressure, that you must assign the recursive result back to node.left and node.right? Will you remember that the pruning check comes after both recursive calls, not before? Or will you accidentally write a pre-order solution that checks the node before its children have been processed?

Understanding is not recall. You understood the solution. Recall means you can write it cold, from memory, without mixing up the traversal order or forgetting to reassign the children.

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 two recursive calls with reassignment, and the pruning condition from memory. After a few repetitions, the post-order-transform pattern and the return-value-signal pattern are automatic.

These two 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

• Subtree of Another Tree - Reasoning about subtrees as self-contained units. A prerequisite for understanding when an entire subtree should be kept or removed.
• Invert Binary Tree - Another tree transformation problem where you modify the tree structure recursively. Uses pre-order instead of post-order.
• Balanced Binary Tree - Bottom-up tree validation where the return value signals both height and failure. The same return-value-as-signal idea.