Binary Tree Pruning - Solution & Explanation

Problem Overview: Given a binary tree containing only 0 and 1, remove every subtree that does not contain a 1. If a subtree is made entirely of zeros, it should be pruned from the parent. The result is a modified tree where every remaining subtree contains at least one 1.

Approach 1: Post-order Traversal (DFS) (Time: O(n), Space: O(h))

The cleanest solution uses post-order traversal with recursion. In post-order, you process the left and right children before evaluating the current node. This order is critical because whether a node should be pruned depends on whether its children contain a 1. Recursively prune the left subtree and assign the result to root.left, then do the same for the right subtree. After both recursive calls return, check the current node: if root.val == 0 and both children are null, the entire subtree contains only zeros and should be removed by returning null.

This approach works because every subtree is evaluated bottom-up. By the time you process a node, its children have already been cleaned. The algorithm visits each node exactly once, giving O(n) time complexity where n is the number of nodes. Recursion depth depends on tree height, so the space complexity is O(h). This method relies on classic Depth-First Search over a Binary Tree, making it both concise and interview-friendly.

Approach 2: Iterative Post-order Traversal (Time: O(n), Space: O(h))

The same pruning logic can be implemented iteratively using an explicit stack to simulate post-order traversal. Maintain a stack of nodes along with a visited flag or use two-stack traversal. The goal is to ensure children are processed before their parent. Once both children of a node have been handled, check whether they were pruned and determine if the current node should also be removed.

This approach avoids recursion and is useful in environments where recursion depth may exceed stack limits. Each node is pushed and popped from the stack at most once, so the total runtime remains O(n). Auxiliary stack space grows with the height of the tree, resulting in O(h) space complexity. The underlying idea is still the same bottom-up evaluation commonly used in Tree dynamic processing problems.

Recommended for interviews: The recursive post-order traversal is the expected solution. It expresses the pruning rule directly: process children first, then decide whether the current node survives. Interviewers typically look for this bottom-up reasoning because it shows you understand how subtree information flows upward. The iterative version demonstrates deeper knowledge of traversal mechanics but is rarely required unless recursion limits are discussed.