Domain 2MediumMEDIUM

Binary Tree Pruning

Prune a binary tree of 0s and 1s by removing subtrees that do not contain any `1`s using post-order traversal recursion.

Domain: medium•Updated: 2026-09-01
#recursion#binary-tree#O(n)#DFS

Problem Breakdown

We are given the root node of a binary tree where every node’s value is either 0 or 1. The objective is to prune (remove) any subtree that does not contain at least one 1.

Key Inputs & Outputs:

  • Input: A pointer (TreeNode) representing the head of the binary tree.
  • Output: The new root pointer after pruning invalid subtrees. Note that we modify pointers in-place and return references to existing nodes where possible, or None if a branch is entirely pruned.

Implicit Constraints & Edge Cases:

  • Empty Tree: If root is initially None, the result must be None.
  • All Zeros: A tree consisting entirely of 0s should return None (the root itself gets pruned).
  • Single Node:
    • [1]: Returns the node.
    • [0]: Returns None.
  • Structure Modification: We update pointers (left, right) to point to valid children or None based on recursive results, effectively pruning in-place before returning up the stack.

Intuition

A naive approach might be to traverse every node and count how many 1s exist in its entire subtree (including itself). If the count is zero, we prune that branch. However, counting for each node independently would lead us back into a brute-force complexity of O(N2)O(N^2) because calculating counts repeatedly overlaps work unnecessarily.

The Key Insight: This problem requires information from children to make decisions about parents. Specifically, before deciding whether the current node should be kept or pruned, we must know if its left and right subtrees contain any 1s. This suggests a Post-Order Traversal (Bottom-Up) approach using recursion:

  1. Recursively process the left child first to get back the valid head of that subtree (or None if it was all pruned).
  2. Do the same for the right child.
  3. Update current node’s pointers based on what we got from children.
  4. Finally, decide whether this specific node should be kept or removed: If its value is 0 AND both children are now effectively empty (pruned), then this subtree contains no 1s and must also be pruned (return None). Otherwise, keep the current node (return self).

Approach

We will implement a recursive helper function that returns either the valid root of a pruned subtree or None if the entire branch should be removed.

Algorithm Steps:

  1. Base Case: If the current node is None, return None.
  2. Recursive Step (Bottom-Up):
    • Call the function on node.left. Store result in a variable, say left_child.
    • Call the function on node.right. Store result in a variable, say right_child.
  3. Prune Children: Update node.left and node.right to point to these results (which might be None).
  4. Decide Current Node’s Fate:
    • If the current node’s value is 0, AND both children are now effectively empty (left_child is None), then this subtree contains no 1s at all. Return None.
    • Otherwise (if there was a 1 in one of the subtrees, or if the current node itself is 1), return the current node object so it can be attached to its parent.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes. We visit every node exactly once during the post-order traversal.
  • Space Complexity: O(H)O(H) for recursion stack space, where HH is the height of the tree. In a skewed tree (worst case), this becomes O(N)O(N). Given the constraint (N≤200N \le 200), this fits well within memory limits without risk of overflow.

Solution

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: 'TreeNode') -> 'TreeNode':
        # Base case: if node is None, return None (empty subtree)
        if not root:
            return None
        
        # Recursively process children first (Post-order traversal)
        left = self.pruneTree(root.left)
        right = self.pruneTree(root.right)
        
        # Update pointers to the pruned results from recursion
        root.left = left
        root.right = right
        
        # If current node is 0 and both children are now None (pruned), 
        # this subtree contains no 1s, so we must prune it too.
        if not root.val and not left and not right:
            return None
            
        # Otherwise, keep the current node (it either has a 1 or connects to one)
        return root

Edge Cases Handled

  • Empty Input (root is None): The base case immediately returns None, correctly handling an empty tree.
  • All Zeros: If every branch eventually leads back up with children being None and the current node value being 0, the condition at step 4 triggers, returning None. This handles a single [0] or deep trees of zeros correctly by pruning everything down to nothing.
  • Single Node (1): Recursion hits base case for missing children (returns None). Current val is 1. Condition fails (val != 0), returns node. Correctly keeps the tree.
  • Deep Skewed Tree: The recursion depth matches the height of the tree (O(N)O(N) stack space). Since N≤200N \le 200, this does not hit Python’s default recursion limit and is efficient enough for production constraints here.