Problem Description

You are given the root of a binary tree containing digits from 0 to 9.
Each root-to-leaf path in the tree represents a number formed by concatenating the digits along that path.

Return the total sum of all root-to-leaf numbers.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf numbers are 12 and 13.
Sum = 12 + 13 = 25

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf numbers are 495, 491, and 40.
Sum = 495 + 491 + 40 = 1026

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 9.

---

Intuition

Each path from the root to a leaf node forms a number.
At each node, the number being formed can be represented as:

currentNumber = previousNumber * 10 + node.val

We perform a Depth-First Search (DFS) to traverse all root-to-leaf paths, maintaining the running number as we go deeper into the tree.
When we reach a leaf node, we add the full number to our total sum.

---

Approach 1: Recursive Depth-First Search (DFS)

Idea

We start from the root with an initial value of 0.
At each step:

1. Multiply the current sum by 10 and add the node’s value.
2. If the node is a leaf (no left and right children), return the number formed.
3. Otherwise, recursively compute the sums from the left and right subtrees.

Finally, return the total of both sides.

---

Algorithm Steps

1. Define a helper function dfs(TreeNode node, int currentSum).
2. If the node is null, return 0.
3. Update the running number: currentSum = currentSum * 10 + node.val.
4. If it’s a leaf, return currentSum.
5. Otherwise, recursively call dfs for both left and right children.
6. Return the sum of both recursive calls.

---

Java Code Implementation

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

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

        currentSum = currentSum * 10 + node.val;

        // If it's a leaf node, return the number formed
        if (node.left == null && node.right == null)
            return currentSum;

        // Otherwise, sum from both subtrees
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
}

---

Example Walkthrough

Input:

root = [4,9,0,5,1]

Tree Structure:

        4
       / \
      9   0
     / \
    5   1

DFS Traversal:

Path	Formed Number	Explanation
4 → 9 → 5	495	Leaf node reached
4 → 9 → 1	491	Leaf node reached
4 → 0	40	Leaf node reached

Sum = 495 + 491 + 40 = 1026

---

Approach 2: Iterative DFS (Using Stack)

If you prefer an iterative method, you can simulate recursion using a stack.

Each stack element contains a node and the number formed till that node.

Java Code

import java.util.Stack;

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();
        nodeStack.push(root);
        sumStack.push(root.val);

        int total = 0;

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int currentSum = sumStack.pop();

            // If it's a leaf, add to total
            if (node.left == null && node.right == null) {
                total += currentSum;
            }

            // Push children with updated values
            if (node.right != null) {
                nodeStack.push(node.right);
                sumStack.push(currentSum * 10 + node.right.val);
            }
            if (node.left != null) {
                nodeStack.push(node.left);
                sumStack.push(currentSum * 10 + node.left.val);
            }
        }

        return total;
    }
}

---

Complexity Analysis

Type	Complexity	Explanation
Time Complexity	O(N)	Each node is visited once
Space Complexity	O(H)	Recursion or stack depth proportional to tree height (H ≤ N)

---

Edge Cases

1. Single Node Tree Input: [7] Output: 7
2. Tree with Only Left Children Input: [1,2,3,4] Output: 1234
3. Tree with Zeros Input: [1,0,3] Output: 13

---

Summary

• This problem uses DFS traversal to accumulate numbers from root to leaf.
• Recursive DFS is simpler and clean.
• Each path represents a unique number formed by concatenation.
• The total sum is obtained by summing all such numbers.