LeetCode 1022: Sum of Root To Leaf Binary Numbers

Problem Restatement

We are given the root of a binary tree where each node has value 0 or 1.

Each root-to-leaf path represents a binary number.

We need to return the sum of all these binary numbers.

The official constraints state that the number of nodes is in [1, 1000], Node.val is 0 or 1, and the answer fits in a 32-bit integer.

Input and Output

Function shape:

def sumRootToLeaf(root: Optional[TreeNode]) -> int:
    ...

Examples

Example 1:

root = [1, 0, 1, 0, 1, 0, 1]

The tree looks like:

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

Paths and their binary values:

Sum = 4 + 5 + 6 + 7 = 22.

Answer:

22

Key Insight

As we walk from root to a leaf, we accumulate the binary number bit by bit.

When we move to a child, the current number shifts left (multiply by 2) and the child’s value is appended.

When we reach a leaf, the accumulated value is one of the binary numbers to sum.

Algorithm

Define a recursive DFS function dfs(node, current):

1. If node is None, return 0.
2. current = current * 2 + node.val.
3. If node is a leaf, return current.
4. Return dfs(node.left, current) + dfs(node.right, current).

Correctness

At each node, current holds the binary number formed by the path from the root to that node.

Multiplying by 2 shifts the binary digits left, and adding node.val appends the new bit.

At a leaf, the accumulated value is the complete binary number for that root-to-leaf path.

Edge Cases

• A missing child should not contribute a fake value to min/max or path computations.
• Leaf nodes often define the base case; verify the behavior on a single-node tree.
• When passing state down the tree, update it before visiting children that depend on the current node.

Complexity

Let n be the number of nodes.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from typing import Optional

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

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current: int) -> int:
            if node is None:
                return 0
            current = current * 2 + node.val
            if node.left is None and node.right is None:
                return current
            return dfs(node.left, current) + dfs(node.right, current)

        return dfs(root, 0)

Code Explanation

Accumulate the binary value as we descend:

current = current * 2 + node.val

Return the accumulated value when reaching a leaf:

if node.left is None and node.right is None:
    return current

Otherwise, sum the results from left and right subtrees:

return dfs(node.left, current) + dfs(node.right, current)

Testing

def run_tests():
    root1 = TreeNode(1,
        TreeNode(0, TreeNode(0), TreeNode(1)),
        TreeNode(1, TreeNode(0), TreeNode(1))
    )
    s = Solution()
    assert s.sumRootToLeaf(root1) == 22

    root2 = TreeNode(0)
    assert s.sumRootToLeaf(root2) == 0

    root3 = TreeNode(1, TreeNode(1))
    assert s.sumRootToLeaf(root3) == 3

    print("all tests passed")

run_tests()