Sum of Root To Leaf Binary Numbers: Tree DFS Pattern

Given the root of a binary tree where each node has a value of 0 or 1, each root-to-leaf path represents a binary number (most significant bit at the root). Return the sum of all root-to-leaf binary numbers.

This is LeetCode 1022: Sum of Root To Leaf Binary Numbers. For example, in the tree below, the three root-to-leaf paths form binary strings "100" (4), "101" (5), and "111" (7). The answer is 4 + 5 + 7 = 16.

Why this problem matters

This problem sits at the intersection of tree traversal and bit manipulation, two topics that come up constantly in interviews. You need to carry state downward through a DFS while building a number one bit at a time. That same "accumulate a value as you descend" pattern appears in Sum Root to Leaf Numbers (the decimal version), Path Sum, and many other tree problems. Learning it here with binary numbers makes the bit-shifting intuition click, which pays off whenever you see binary representations in tree or recursion problems.

The key insight

As you move from a parent node to a child, the binary number you have been building so far needs to shift left by one position to make room for the new bit. That is exactly what multiplying by 2 does. Then you add the child's value (0 or 1) to fill in the new rightmost bit.

In other words, at each node: current_val = current_val * 2 + node.val.

You can also write this with bitwise operations: current_val = (current_val << 1) | node.val. Both forms do the same thing. The multiplication version is easier to read, and the bitwise version makes the binary nature explicit.

When you reach a leaf, current_val holds the complete decimal value of that root-to-leaf binary number. Add it to a running total.

The solution

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

Here is what each piece does:

• dfs(node, current_val) takes the current tree node and the binary number accumulated so far from the root down to this node's parent.
• current_val = current_val * 2 + node.val shifts the accumulated value left by one bit and appends the current node's bit.
• The leaf check if not node.left and not node.right fires when both children are None. At that point current_val is the full binary number for this path, so you return it.
• For internal nodes, you return the sum of the left subtree's total and the right subtree's total. Each child will continue building on the same current_val.
• dfs(root, 0) starts the recursion with an accumulated value of 0.

Visual walkthrough

Let's trace through the DFS on the tree [1, 0, 1, 0, 1, null, 1] and watch current_val build up at each node.

Notice how the value doubles at each level. The root starts at 1. Going left to 0 gives 1 * 2 + 0 = 2. Going left again to 0 gives 2 * 2 + 0 = 4. That final 4 is exactly the decimal value of binary "100". The pattern holds for every path.

Complexity analysis

Time is O(n) where n is the number of nodes. You visit every node exactly once and do O(1) work at each node (one multiplication, one addition, one leaf check).

Space is O(h) where h is the height of the tree. The recursion stack holds at most h frames at any given time. For a balanced tree, h = log n. For a completely skewed tree, h = n.

The building blocks

1. Pre-order state passing

You carry current_val downward from root to leaf. Each node transforms the value (multiply by 2 and add the bit) before passing it to its children. This is the pre-order accumulation pattern: process the current node's contribution first, then recurse into children with the updated state. The same pattern appears in Sum Root to Leaf Numbers (using * 10 instead of * 2) and Path Sum (subtracting from a target).

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

2. Binary number construction via bit shifting

Building a binary number one bit at a time is the core arithmetic trick. Each time you see a new bit, you shift the existing number left and OR (or add) the new bit. Starting from 0, the sequence of operations for the path 1, 0, 1 looks like: 0 * 2 + 1 = 1, then 1 * 2 + 0 = 2, then 2 * 2 + 1 = 5. And indeed, binary "101" equals 5.

def build_binary(bits):
    val = 0
    for b in bits:
        val = val * 2 + b
    return val

Edge cases

• Single node (root is a leaf). The tree has one node with value 0 or 1. The answer is just that value.
• Left-skewed tree. There is only one root-to-leaf path. The DFS follows the chain all the way down, building the binary number, and returns it directly.
• All zeros. Every node has value 0. Each path's binary number is 0, so the total sum is 0.
• All ones. A complete binary tree of all 1s. Each path of depth d produces a binary number with d ones, which equals 2^d - 1. The sum depends on the tree shape.
• Tree with one child missing. Be careful: a node with only a left child (and no right child) is not a leaf. Only nodes with both children missing count as leaves.

From understanding to recall

You just watched the DFS carry current_val downward, doubling it and adding each node's bit at every level. At each leaf, the accumulated value was the exact decimal representation of the root-to-leaf binary string. The pattern is clean: multiply by 2, add the bit, recurse.

But will you remember the current_val * 2 + node.val formula under interview pressure? Will you remember to check for leaves (not just null nodes) before adding to the sum? Will you instinctively pass the accumulated value as a parameter rather than trying to build it bottom-up?

Spaced repetition builds that recall. You type the solution from scratch at increasing intervals: after a day, then three days, then a week. Each time, you reconstruct the DFS helper, the accumulation step, and the leaf check from memory. After a few rounds, the pattern becomes automatic.

Pre-order state passing is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Sum Root to Leaf Numbers - The decimal version of this problem, using * 10 instead of * 2 to accumulate values along root-to-leaf paths
• Binary Tree Paths - Collect all root-to-leaf paths as strings, using the same DFS traversal pattern
• Path Sum - The foundational pre-order state passing problem where you carry a running target downward and check a condition at leaves

CodeBricks breaks problems like Sum of Root To Leaf Binary Numbers into the building blocks behind them, then uses spaced repetition to make those blocks automatic. If you want to stop re-solving the same patterns and start recognizing them on sight, give it a try.