---

1. Problem Summary

You are given the root of a binary tree where each node has a value of:

0 or 1

Your task is to:

Remove (prune) every subtree that does not contain at least one node with value 1.

Rules and clarifications:

• A subtree is considered removable if all nodes within it are 0.
• Pruning may affect parent nodes if they become leaf-zero nodes afterward.
• Return the updated root after pruning.
• If the entire tree contains no 1s, return null.

Example:

Input:

       1
      / \
     0   0
    / \
   0   0

After pruning, output:

1

Another example:

Input:

       1
      / \
     0   1
      \
       1

After pruning, output:

       1
      / \
         1

---

2. Key Insights

Insight 1: Pruning depends on subtree contents

A node should remain only if:

• its value is 1, OR
• at least one of its children contains a 1

Insight 2: Post-order traversal is ideal

We must evaluate children before deciding if parent remains.

Order:

recurse left → recurse right → evaluate current node

Insight 3: Returning null prunes subtree

If both pruned children are null and node value is 0 → return null.

Insight 4: No need to count values

Binary condition is enough.

Insight 5: Tree structure preserved for valid subtrees

We modify pointers but do not create new nodes.

---

3. Approach

Recursive post-order pruning

Steps:

1. If current node is null, return null
2. Recursively prune left subtree
3. Recursively prune right subtree
4. Update node.left and node.right using recursive results
5. If: node.val == 0 AND node.left == null AND node.right == null return null (prune)
6. Else return node

---

4. Time and Space Complexity

Time Complexity:

O(N)

Every node visited exactly once

Space Complexity:

O(H)

Where H = height of tree (recursion stack)

Worst case unbalanced: O(N)
Balanced tree: O(log N)

---

5. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        if (root.val == 0 && root.left == null && root.right == null) {
            return null;
        }

        return root;
    }
}

---

6. Dry Run Examples

Example 1

Input:

[1,null,0,0,1]

Tree:

    1
     \
      0
     / \
    0   1

Pruning:

• left of 0 → prune
• right of 0 → keep (1 present)
• root kept

Output:

[1,null,0,null,1]

---

Example 2

Input:

[0,0,0]

Tree:

   0
  / \
 0   0

All zero → entire tree removed

Output:

null

---

Example 3

Input:

[1,1,0,0,0,0,1]

Tree:

        1
       / \
      1   0
     / \   \
    0   0   1

Result:

        1
       / \
      1   0
           \
            1

Output keeps only meaningful subtrees.

---

Example 4

Input:

[1]

Output:

[1]

---

Example 5

Input:

[0]

Output:

null

---

7. Why This Solution Works

• Post-order ensures children evaluated before pruning
• Eliminates zero-only subtrees correctly
• No unnecessary storage or traversal
• Handles full, partial, and empty prunes
• Works for any tree shape

---

8. Common Mistakes

1. Using preorder traversal (prunes too early)
2. Forgetting to reassign: root.left = ... root.right = ...
3. Checking only node value, not subtree content
4. Attempting to count number of ones (unnecessary)
5. Returning original nodes without structural update