Problem statement

Every node of a binary tree holds a single bit, 0 or 1. Each path from the root down to a leaf spells a binary number, most significant bit first — the path 1 → 0 → 1 is 101, which is 5.

Given the root of the tree, return the sum of the numbers spelled by all root-to-leaf paths.

Example 1

Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: The paths read 100, 101, 110 and 111 — that is 4 + 5 + 6 + 7 = 22.

Example 2

Input: root = [0]
Output: 0
Explanation: The only path is the number 0.

Example 3

Input: root = [1,1]
Output: 3
Explanation: One path, 11 in binary.

Constraints

• 1 <= number of nodes <= 1000
• Node.val is 0 or 1
• the answer fits in a signed 32-bit integer

Hints for Sum of Root To Leaf Binary Numbers

1. Hint 1

   Reading one more bit b of a binary number turns the value v read so far into 2 * v + b.

2. Hint 2

   Carry that running value down the tree: each child receives its parent's value, doubled, plus its own bit.

3. Hint 3

   Add the running value to the answer only at leaves — a node with no children ends a path.

How to solve Sum of Root To Leaf Binary Numbers

Appending a bit to a binary number doubles it and adds the bit, so the value of the path to any node is computed from its parent's value in one step. A depth-first walk carries it down and adds it up at the leaves.

Approach

1. Start a depth-first traversal at the root with running value 0.
2. At each node compute cur = 2 * acc + node.val.
3. If the node is a leaf, add cur to the total; otherwise visit both children with cur.
4. Return the total.

Why it works

By induction on depth, cur at a node equals the binary number spelled by the path from the root to that node; at a leaf that is exactly one of the numbers to sum, and every leaf is reached once.

Complexity

• Time — O(n)
• Space — O(h) for the recursion or stack

Pitfalls

• Only leaves end a path: a node with one child must not add its value.
• Do not build the path as a string and parse it — the running value is simpler and avoids long strings.

Reference solution

Python

from typing import Optional

def sumRootToLeaf(root: Optional[TreeNode]) -> int:
    total = 0
    stack = [(root, 0)]
    while stack:
        node, acc = stack.pop()
        cur = acc * 2 + node.val
        if node.left is None and node.right is None:
            total += cur
        if node.left:
            stack.append((node.left, cur))
        if node.right:
            stack.append((node.right, cur))
    return total

Java

public static int sumRootToLeaf(TreeNode root) {
    return pathSum(root, 0);
}

static int pathSum(TreeNode node, int acc) {
    if (node == null) return 0;
    int cur = acc * 2 + node.val;
    if (node.left == null && node.right == null) return cur;
    return pathSum(node.left, cur) + pathSum(node.right, cur);
}

C++

int pathSum(TreeNode* node, int acc);

int sumRootToLeaf(TreeNode* root) {
    return pathSum(root, 0);
}

int pathSum(TreeNode* node, int acc) {
    if (!node) return 0;
    int cur = acc * 2 + node->val;
    if (!node->left && !node->right) return cur;
    return pathSum(node->left, cur) + pathSum(node->right, cur);
}

JavaScript

var sumRootToLeaf = function(root) {
    return pathSum(root, 0);
};

var pathSum = function(node, acc) {
    if (node === null) return 0;
    var cur = acc * 2 + node.val;
    if (node.left === null && node.right === null) return cur;
    return pathSum(node.left, cur) + pathSum(node.right, cur);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy