Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

LeetCode 814 - Binary Tree Pruning

Problem Understanding

This problem asks us to modify a binary tree by removing every subtree that does not contain at least one node with value 1.

A subtree consists of a node and all of its descendants. If an entire subtree contains only 0 values, then that subtree should be deleted from the tree. The final result should preserve all nodes that either:

Have value 1, or
Have at least one descendant with value 1

The input is the root node of a binary tree. Each node contains either 0 or 1. The output should be the root of the pruned tree after all invalid subtrees have been removed.

The constraints are relatively small, with at most 200 nodes. This means even less optimized approaches could technically pass, but the structure of the problem strongly suggests a recursive depth-first traversal because the decision about whether to remove a node depends on information from its children.

The most important observation is that whether a node should remain in the tree depends entirely on its descendants. Specifically:

If both left and right subtrees are removed,
And the current node's value is 0,
Then the current node must also be removed.

This dependency means we cannot correctly process a node before processing its children. That naturally leads to a postorder traversal, where children are processed before the parent.

Several edge cases are important:

The entire tree may contain only zeros, in which case the answer should be null.
A leaf node with value 0 should always be removed.
A node with value 0 must remain if it has a descendant with value 1.
The tree may already satisfy the condition and require no pruning.

Approaches

Brute Force Approach

A brute-force solution would repeatedly scan the tree looking for removable subtrees. For every node, we could perform another traversal to determine whether its subtree contains a 1.

For example, we might:

Traverse every node in the tree.
For each node, recursively check whether its subtree contains a 1.
Remove the subtree if no 1 exists.
Repeat until no more changes occur.

This approach is correct because every subtree is explicitly checked. However, it performs redundant work. The same subtree may be scanned many times during repeated containment checks.

In the worst case, each node could trigger another traversal of most of the tree, leading to quadratic complexity.

Optimal Approach

The key insight is that whether a subtree should remain can be determined during a single postorder traversal.

A node should be deleted only after we know whether its left and right subtrees contain a 1. That means we must process children before the parent.

The recursive strategy is:

Recursively prune the left subtree.
Recursively prune the right subtree.
After pruning children, determine whether the current node should remain.
If the current node has value 0 and both children are null, remove it.

This avoids repeated subtree scans because each node is processed exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly checks whether subtrees contain a 1
Optimal	O(n)	O(h)	Single postorder DFS traversal

Here, n is the number of nodes and h is the tree height.

Algorithm Walkthrough

Start a recursive depth-first traversal from the root node.
For each node, recursively process the left subtree first. The recursive call returns either:

The original subtree root if it should remain, or
null if the subtree should be removed.

Recursively process the right subtree using the same logic.
After both children are processed, update the current node's left and right pointers with the returned values. This effectively removes invalid subtrees.
Determine whether the current node itself should be removed. A node should be deleted if:

Its value is 0
Its left child is null
Its right child is null

This means the entire subtree rooted at this node contains no 1. 6. If the node should be removed, return null. 7. Otherwise, return the current node. 8. The final returned value from the root call becomes the answer.

Why it works

The algorithm works because of postorder traversal. By the time we evaluate a node, both of its subtrees have already been fully pruned. Therefore:

Any remaining child subtree is guaranteed to contain at least one 1.
Any removed child subtree contained no 1.

This guarantees that when we evaluate a node, we have complete information about whether its entire subtree contains a 1.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:
            if not node:
                return None

            node.left = dfs(node.left)
            node.right = dfs(node.right)

            if node.val == 0 and not node.left and not node.right:
                return None

            return node

        return dfs(root)

The implementation follows the recursive postorder strategy directly.

The helper function dfs processes one subtree at a time. If the current node is None, it immediately returns None.

The recursive calls:

node.left = dfs(node.left)
node.right = dfs(node.right)

prune both child subtrees before evaluating the current node.

After pruning the children, the code checks:

if node.val == 0 and not node.left and not node.right:

This condition means:

The current node is 0
No valid descendants remain

Therefore, the subtree contains no 1, so it should be deleted by returning None.

Otherwise, the current node remains part of the final tree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pruneTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    root.Left = pruneTree(root.Left)
    root.Right = pruneTree(root.Right)

    if root.Val == 0 && root.Left == nil && root.Right == nil {
        return nil
    }

    return root
}

The Go implementation is structurally identical to the Python version. Since Go uses pointers for tree nodes, returning nil effectively removes a subtree.

Unlike Python, Go does not have truthy or falsy object evaluation, so explicit nil comparisons are required:

root.Left == nil && root.Right == nil

There are no integer overflow concerns because node values are restricted to 0 and 1.

Worked Examples

Example 1

Input:

[1,null,0,0,1]

Tree structure:

We process nodes bottom-up.

Current Node	Left Result	Right Result	Action
0 (left leaf)	null	null	Remove node
1 (right leaf)	null	null	Keep node
0 (parent)	null	1	Keep node
1 (root)	null	0	Keep node

Final tree:

Output:

[1,null,0,null,1]

Example 2

Input:

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

Tree structure:

Process leaves first.

Current Node	Result
Leftmost 0	Removed
Second 0	Removed
Third 0	Removed
Rightmost 1	Kept

Now process internal nodes:

Current Node	Left Child	Right Child	Action
Left internal 0	null	null	Remove
Right internal 1	null	1	Keep
Root 1	null	1	Keep

Final tree:

Output:

[1,null,1,null,1]

Example 3

Input:

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

Tree structure:

         1
       /   \
      1     0
     / \   / \
    1   1 0   1
   /
  0

The leaf node with value 0 under the left subtree gets removed because it contains no 1.

The internal 0 node in the right subtree also gets removed.

However, the right subtree root remains because it still has a child containing 1.

Final output:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(h)	Recursive call stack stores at most tree height frames

The algorithm performs a single DFS traversal. Every node is processed once, and each operation at a node takes constant time.

The space complexity comes from recursion depth. In a balanced tree, the height is O(log n). In the worst case of a skewed tree, the height becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    if not root:
        return None

    result = []
    queue = [root]

    while queue:
        node = queue.pop(0)

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

solution = Solution()

# Example 1
root = TreeNode(1, None,
    TreeNode(0,
        TreeNode(0),
        TreeNode(1)
    )
)
assert serialize(solution.pruneTree(root)) == [1, None, 0, None, 1]  # basic pruning

# Example 2
root = TreeNode(1,
    TreeNode(0,
        TreeNode(0),
        TreeNode(0)
    ),
    TreeNode(1,
        TreeNode(0),
        TreeNode(1)
    )
)
assert serialize(solution.pruneTree(root)) == [1, None, 1, None, 1]  # multiple removals

# Example 3
root = TreeNode(1,
    TreeNode(1,
        TreeNode(1,
            TreeNode(0)
        ),
        TreeNode(1)
    ),
    TreeNode(0,
        TreeNode(0),
        TreeNode(1)
    )
)
assert serialize(solution.pruneTree(root)) == [1, 1, 0, 1, 1, None, 1]  # mixed pruning

# Single node with value 0
root = TreeNode(0)
assert solution.pruneTree(root) is None  # entire tree removed

# Single node with value 1
root = TreeNode(1)
assert serialize(solution.pruneTree(root)) == [1]  # tree remains unchanged

# All zeros tree
root = TreeNode(0,
    TreeNode(0),
    TreeNode(0)
)
assert solution.pruneTree(root) is None  # everything removed

# Zero root with one valid descendant
root = TreeNode(0,
    TreeNode(0),
    TreeNode(1)
)
assert serialize(solution.pruneTree(root)) == [0, None, 1]  # root preserved because subtree has 1

# Deep skewed tree
root = TreeNode(0,
    TreeNode(0,
        TreeNode(0,
            TreeNode(1)
        )
    )
)
assert serialize(solution.pruneTree(root)) == [0, 0, None, 0, None, 1]  # recursive depth handling

Test	Why
`[1,null,0,0,1]`	Validates basic subtree pruning
`[1,0,1,0,0,0,1]`	Tests multiple subtree removals
`[1,1,0,1,1,0,1,0]`	Tests mixed preservation and pruning
Single node `0`	Ensures entire tree can disappear
Single node `1`	Ensures valid tree remains unchanged
All zeros tree	Verifies complete pruning
Root `0` with descendant `1`	Ensures ancestor preservation
Deep skewed tree	Tests recursion on unbalanced trees

Edge Cases

One important edge case is a tree consisting entirely of zeros. In this situation, every subtree lacks a 1, so the entire tree must be removed. A naive implementation might incorrectly preserve the root or fail to propagate removals upward. The recursive solution handles this naturally because every leaf 0 is removed first, eventually causing the root itself to satisfy the removal condition.

Another important edge case is a node with value 0 that has a descendant containing 1. It might seem intuitive to remove the node immediately because its own value is 0, but that would incorrectly disconnect valid parts of the tree. The algorithm avoids this mistake by pruning children first. If any descendant subtree remains, then the parent node must also remain to preserve connectivity.

A third edge case involves leaf nodes. A leaf node with value 0 should always be removed because it contains no descendants and no 1. Conversely, a leaf node with value 1 must always remain. The condition:

node.val == 0 and not node.left and not node.right

correctly distinguishes these two situations.

A final edge case is a highly unbalanced tree that resembles a linked list. Recursive tree algorithms can sometimes fail on deep recursion if constraints are very large. However, the problem limits the tree to 200 nodes, so recursion depth remains safe for both Python and Go implementations.