1. Problem Summary

You are given the root of a binary tree where each node contains a value of either 0 or 1.
Every path from the root to a leaf forms a binary number, where the digits are collected in the order they appear along the path.

Your task is to compute the sum of all such binary numbers, converting each to decimal, and return the total.

A leaf node is a node with no left and no right child.

Example:
A path 1 → 0 → 1 represents binary 101, which equals 5 in decimal.

---

2. Key Insights

Binary interpretation along traversal

As we move down the tree:

• Appending a bit in binary is equivalent to: current = current * 2 + node.val

DFS fits naturally

We must preserve path state while descending, and evaluate at leaves.

No need to store full paths

We compute the numeric value incrementally.

---

3. Approach

Depth-First Search (DFS)

1. Start from the root with initial value 0.
2. At each node, update accumulated value: next = current * 2 + node.val
3. If at a leaf, add next to the running total.
4. Recursively explore left and right children.
5. Return the final accumulated sum.

---

4. Time and Space Complexity

Time Complexity: O(N)

Every node is processed exactly once.

Space Complexity:

• O(H) recursion depth
• Worst case (skewed tree): O(N)
• Best case (balanced tree): O(log N)

---

5. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int current) {
        if (node == null) {
            return 0;
        }

        current = current * 2 + node.val;

        // If leaf node, return the constructed number
        if (node.left == null && node.right == null) {
            return current;
        }

        // Sum from left and right subtrees
        return dfs(node.left, current) + dfs(node.right, current);
    }
}

---

6. Dry Run Example

Consider the tree:

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

Path evaluations:

Path 1:

1 → 0 → 0
Binary: 100
Decimal: 4

Path 2:

1 → 0 → 1
Binary: 101
Decimal: 5

Path 3:

1 → 1 → 0
Binary: 110
Decimal: 6

Path 4:

1 → 1 → 1
Binary: 111
Decimal: 7

Running Sum:

4 + 5 + 6 + 7 = 22

Step-by-step accumulation on one path:

Path: 1 → 0 → 1
Initial: current = 0

At root (1):
current = 0 * 2 + 1 = 1

At next node (0):
current = 1 * 2 + 0 = 2

At leaf (1):
current = 2 * 2 + 1 = 5

Add 5 to total.