Binary Tree Pruning — LeetCode 814 Post-Order Recursion

Problem Statement#

Given the root of a binary tree where each node has a value of 0 or 1, remove every subtree (rooted anywhere) that does not contain a 1. Return the modified root.

Constraints:

• The number of nodes in the tree is in the range [1, 200]
• Node.val is 0 or 1

Input:  root = [1,null,0,0,1]
Output: [1,null,0,null,1]

Input:  root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Why This Problem Matters#

LeetCode 814 — Binary Tree Pruning — is a clean post-order recursion problem that interviewers at Amazon, Google, and Apple use to test whether candidates can mutate trees safely while traversing them. It looks deceptively simple until you realize you must process children before deciding whether to keep the parent — the textbook definition of post-order.

This problem reflects real engineering tasks: pruning empty branches in feature flag trees, dead-code elimination in compiler ASTs, and removing zero-traffic nodes in CDN routing trees. Recognizing post-order as the right traversal — and being comfortable nulling out child pointers — is a mark of a fluent tree programmer.

The Core Insight#

A subtree should be removed if and only if every node in it is 0. Equivalently, we keep a node if node.val == 1 or any of its descendants is 1. Recurse on the children first (post-order), null them out if their result is "no 1 found", and return whether the current subtree contains a 1.

The cleanest formulation: containsOne(node) returns true if the subtree rooted at node contains any 1, and as a side effect prunes children whose subtrees contain no 1.

Visual Dry Run#

For tree [1, 0, 1, 0, 0, 0, 1]:

Final tree: [1, null, 1, null, 1].

Solution (Optimal)#

from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def contains_one(node: Optional[TreeNode]) -> bool:
            if node is None:
                return False
            left_has = contains_one(node.left)
            right_has = contains_one(node.right)
            if not left_has:
                node.left = None
            if not right_has:
                node.right = None
            return node.val == 1 or left_has or right_has
 
        return root if contains_one(root) else None

var pruneTree = function(root) {
    const containsOne = (node) => {
        if (!node) return false;
        const leftHas = containsOne(node.left);
        const rightHas = containsOne(node.right);
        if (!leftHas) node.left = null;
        if (!rightHas) node.right = null;
        return node.val === 1 || leftHas || rightHas;
    };
    return containsOne(root) ? root : null;
};

Time: O(n) — every node is visited once. Space: O(h) — recursion stack proportional to tree height.

Common Mistakes#

• Pre-order pruning: deciding to keep or remove the parent before checking children leaves orphaned 1s.
• Returning the modified subtree directly works, but the boolean version is cleaner and avoids re-checking values.
• Forgetting the root case: if the entire tree contains only zeros, return None, not the original root.
• Mutating during traversal in iterative BFS without careful child tracking — recursion is much safer here.
• Assuming values can be larger than 1 — re-read the constraints: only 0 or 1.

Interview Tips#

• State the post-order intent up front: "I need to know about my children before I decide my own fate."
• Walk through one full sub-case on the whiteboard.
• Mention that the same pattern handles "remove subtrees whose sum is zero" or "remove leaves with value v" (LC 1325).
• Discuss the iterative variant briefly: it requires a parent-pointer stack, which is harder to get right under interview pressure.

Follow-up Questions#

• "Generalize: prune any subtree whose values are all in set S" — Same shape, different leaf check.
• "Prune subtrees with sum equal to 0" — Compute subtree sums post-order, prune accordingly.
• "Iterative version" — Use an explicit stack with parent references and a visited flag.
• "Multi-valued tree where 1 is replaced by has feature flag" — Bit set per node, prune when all bits zero.
• "Prune in-place but preserve original via clone" — Deep copy first, then prune the copy.

Key Takeaways#

• LeetCode 814 Binary Tree Pruning is a post-order recursion that runs in O(n) time and O(h) space.
• A subtree is pruned if and only if every node in it is 0.
• Process children before deciding the parent's fate — that's the textbook post-order signature.
• Return a boolean "contains one?" to keep the recursion clean and avoid extra subtree returns.
• This pattern is used in compiler dead-code elimination and feature-flag tree compaction.
• Amazon, Google, and Apple use this as a phone screen tree-mutation question.
• LC 1325 Delete Leaves With a Given Value uses a near-identical post-order template.