Skip to main content

814 - Binary Tree Pruning

Difficulty: Medium | Pattern: Tree DFS (Post-order) | Company tags: Amazon, Google, Microsoft

Problem Statement​

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Example 1:

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

Example 2:

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

Solution: DFS Post-order — O(n), O(h)​

Key insight: Post-order (process children before parent). After processing subtrees, if a node has no 1 in its subtree, return None to prune it.

def pruneTree(root):
    if not root:
        return None
    
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    
    # Prune if this node is 0 and both children are already pruned (None)
    if root.val == 0 and not root.left and not root.right:
        return None
    
    return root

Dry Run​

    1
     \
      0
     / \
    0   1
  • pruneTree(leaf 0 left): val=0, no children → return None
  • pruneTree(leaf 1 right): val=1, no children → return self (1)
  • pruneTree(node 0): left=None, right=1-node; val=0 but has right child → keep
  • pruneTree(root 1): left=None, right=0-node; has child → keep

Result: 1 → right: 0 → right: 1 ✓

Why Post-order?​

We need to know if any child has a 1 before deciding whether to prune the current node. Post-order gives us bottom-up information.

Complexity​

  • Time: O(n) — visit every node once
  • Space: O(h) — recursion stack