Sum of Root To Leaf Binary Numbers: DFS Binary Accumulation

You are given a binary tree where every node has a value of either 0 or 1. Each root-to-leaf path in the tree represents a binary number, with the root being the most significant bit. Return the sum of all these binary numbers.

This is LeetCode 1022: Sum of Root To Leaf Binary Numbers, an easy problem that tests whether you can combine tree traversal with binary number construction. The trick is not to collect each path and convert it after the fact. Instead, you build the binary value incrementally as you traverse down each path.

Why this problem matters

Binary trees and binary numbers are two fundamental concepts in computer science, and this problem ties them together neatly. It teaches you how to accumulate a value along a path in a tree, which is a pattern that comes up in many tree problems beyond just binary encoding.

More importantly, the incremental binary accumulation technique here, current_sum * 2 + node.val, is the same bit-shifting logic you would use to parse a binary string into an integer. Learning to apply it during a DFS traversal gives you a reusable tool for any problem where you need to build a number digit by digit along a path.

The brute force approach

You could collect every root-to-leaf path as a list of digits, then convert each list from binary to decimal and sum them up.

def sumRootToLeaf(root):
    paths = []

    def dfs(node, path):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right:
            paths.append(list(path))
        dfs(node.left, path)
        dfs(node.right, path)
        path.pop()

    dfs(root, [])
    total = 0
    for path in paths:
        num = 0
        for bit in path:
            num = num * 2 + bit
        total += num
    return total

This works, but it stores every path explicitly. You are using O(n) extra space for all the paths and doing two passes: one to collect and one to convert. You can do better.

The key insight: build the number as you go

Instead of collecting paths and converting them later, pass the running binary value down through the recursion. At each node, update the value with current_sum * 2 + node.val. This is equivalent to shifting the current bits left by one position and appending the new bit.

For example, if you have built up the binary value 10 (which is 2 in decimal) and you visit a node with value 1, the new value is 2 * 2 + 1 = 5, which is 101 in binary. The multiplication by 2 shifts the bits left, and adding the node value fills in the new least significant bit.

Walking through it step by step

Consider a tree with root 1, left child 0, right child 1, and leaves 0, 1, 0, 1 under those children. The four root-to-leaf paths are:

• 1 -> 0 -> 0 which is binary 100 = 4
• 1 -> 0 -> 1 which is binary 101 = 5
• 1 -> 1 -> 0 which is binary 110 = 6
• 1 -> 1 -> 1 which is binary 111 = 7

The total sum is 4 + 5 + 6 + 7 = 22.

At each node, the DFS carries the accumulated value. When it reaches a leaf, it adds that value to the total. No path lists, no post-processing.

The DFS solution

def sumRootToLeaf(root):
    def dfs(node, current_sum):
        if not node:
            return 0
        current_sum = current_sum * 2 + node.val
        if not node.left and not node.right:
            return current_sum
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)

    return dfs(root, 0)

Here is what each piece does:

1. Start the DFS from the root with current_sum = 0.
2. At each node, update current_sum by shifting left and appending the current bit: current_sum * 2 + node.val.
3. If the node is a leaf (no children), return current_sum. This is the decimal value of one complete root-to-leaf binary number.
4. If the node is not a leaf, recurse into both children and return the sum of their results.
5. The base case if not node: return 0 handles when a node has only one child, so the missing side contributes nothing.

Complexity analysis

No extra data structures are needed. The running sum is passed as a parameter, and the results bubble up through return values.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. DFS with accumulated state

The pattern of passing a value down through a recursive tree traversal, updating it at each level:

def dfs(node, accumulated):
    if not node:
        return base_value
    accumulated = update(accumulated, node.val)
    if is_leaf(node):
        return process(accumulated)
    return combine(dfs(node.left, accumulated), dfs(node.right, accumulated))

In Sum of Root To Leaf Binary Numbers, the accumulator is the running binary value and the update is * 2 + node.val. In Path Sum, the accumulator is the running total and the update is + node.val. In Binary Tree Paths, the accumulator is the path string. The skeleton is the same: carry state downward through the recursion and process it at leaves.

2. Binary number construction

The pattern of building an integer from its binary digits one bit at a time:

value = 0
for bit in bits:
    value = value * 2 + bit

This is how you parse any binary representation into a decimal integer without needing to know the total length in advance. In this problem, the "bits" come from tree nodes along a path. In string parsing problems, they come from characters. The core mechanic is identical: shift left and add the new bit.

Edge cases

Before submitting, make sure your solution handles these:

• Single node tree with value 1: there is one path containing just the root. The binary number is 1, so the answer is 1.
• Single node tree with value 0: the answer is 0.
• All zeros where every node is 0: every root-to-leaf path is all zeros, so the total sum is 0.
• All ones where every node is 1: each path represents a binary number like 111...1. Make sure the accumulation does not overflow (not an issue in Python, but relevant in other languages).
• Skewed tree where every node has only one child: there is exactly one root-to-leaf path. The recursion depth equals the number of nodes.
• Large tree with up to 1000 nodes (per the constraints): the DFS approach handles this comfortably within time and space limits.

Common mistakes

1. Forgetting the base case for null nodes. If a node has only a left child or only a right child, the missing side is None. Without if not node: return 0, you will get an attribute error trying to access node.val on None.

2. Checking for leaves incorrectly. A leaf is a node with no left child and no right child. If you only check not node.left, you might treat a node with a right child as a leaf and miss the paths through the right subtree.

3. Converting binary after collecting paths. This works but is wasteful. The incremental approach avoids storing paths entirely and converts on the fly.

4. Using string concatenation instead of arithmetic. Building a binary string at each node and converting with int(s, 2) at each leaf works but is slower. The * 2 + bit approach does pure arithmetic and avoids string overhead.

From understanding to recall

You have read the DFS approach and it makes sense. Pass the running binary value down, multiply by 2 and add the bit at each node, return the value at leaves. A few lines of clean recursion.

But under interview pressure, it is easy to fumble the details. Do you return 0 or current_sum for null nodes? Is the leaf check not node or not node.left and not node.right? Do you update current_sum before or after the leaf check? These small decisions trip people up when they have not practiced.

Spaced repetition fixes this. You write the DFS from scratch at increasing intervals until the pattern is automatic. You see "accumulate a value along root-to-leaf paths" and the code flows out without hesitation.

The DFS-with-accumulated-state pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Path Sum - Another tree path problem where you accumulate a value from root to leaf
• Sum Root to Leaf Numbers - Nearly identical structure, but accumulating decimal digits instead of binary digits
• Binary Tree Paths - Enumerating all root-to-leaf paths, the same DFS skeleton with string accumulation

CodeBricks breaks the sum of root to leaf binary numbers LeetCode problem into its DFS accumulated state and binary construction building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree path accumulation question shows up in your interview, you do not think about it. You just write it.