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
Noneif a branch is entirely pruned.
Implicit Constraints & Edge Cases:
- Empty Tree: If
rootis initiallyNone, the result must beNone. - All Zeros: A tree consisting entirely of 0s should return
None(the root itself gets pruned). - Single Node:
[1]: Returns the node.[0]: ReturnsNone.
- Structure Modification: We update pointers (
left,right) to point to valid children orNonebased 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 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:
- Recursively process the left child first to get back the valid head of that subtree (or
Noneif it was all pruned). - Do the same for the right child.
- Update current node’s pointers based on what we got from children.
- Finally, decide whether this specific node should be kept or removed: If its value is
0AND both children are now effectively empty (pruned), then this subtree contains no1s 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:
- Base Case: If the current node is
None, returnNone. - Recursive Step (Bottom-Up):
- Call the function on
node.left. Store result in a variable, sayleft_child. - Call the function on
node.right. Store result in a variable, sayright_child.
- Call the function on
- Prune Children: Update
node.leftandnode.rightto point to these results (which might beNone). - Decide Current Node’s Fate:
- If the current node’s value is
0, AND both children are now effectively empty (left_childis None), then this subtree contains no1s at all. ReturnNone. - Otherwise (if there was a
1in one of the subtrees, or if the current node itself is1), return the current node object so it can be attached to its parent.
- If the current node’s value is
Complexity Analysis
- Time Complexity: where is the number of nodes. We visit every node exactly once during the post-order traversal.
- Space Complexity: for recursion stack space, where is the height of the tree. In a skewed tree (worst case), this becomes . Given the constraint (), 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 (
rootisNone): The base case immediately returnsNone, correctly handling an empty tree. - All Zeros: If every branch eventually leads back up with children being
Noneand the current node value being0, the condition at step 4 triggers, returningNone. 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 is1. Condition fails (val != 0), returns node. Correctly keeps the tree. - Deep Skewed Tree: The recursion depth matches the height of the tree ( stack space). Since , this does not hit Python’s default recursion limit and is efficient enough for production constraints here.