Given a binary tree where each node contains a digit (0-9), each root-to-leaf path represents a numerical value. For instance, the path 1 → 2 → 3 corresponds to the number 123.

The task is to calculate the sum of all numbers represented by root-to-leaf paths.

Note: A leaf node is a node with no children.

Example 1

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:Path 1→2 represents number 12
Path 1→3 represents number 13
Sum = 12 + 13 = 25

Example 2

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
Path 4→9→5 represents number 495
Path 4→9→1 represents number 491
Path 4→0 represents number 40
Sum = 495 + 491 + 40 = 1026

Approach 1: Depth-First Search

The DFS approach traverses the tree from the root, carrying the accumulated numerical value along each path. When a leaf node is reached, the accumulated value is added to the result.

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 (node.left == null && node.right == null) {
            return currentSum;
        }
        
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once.
• Space Complexity: O(n) in the worst case. The recursion stack depth equals the tree height, which can reach n for a skewed tree.

Approach 2: Breadth-First Search

The BFS approach uses two queues: one for nodes and another for their corresponding accumulated values. Starting from the root, we process each node and propagate values to children by multiplying by 10 and adding the child's digit.

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int total = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> valueQueue = new LinkedList<>();
        
        nodeQueue.offer(root);
        valueQueue.offer(root.val);
        
        while (!nodeQueue.isEmpty()) {
            TreeNode current = nodeQueue.poll();
            int accumulated = valueQueue.poll();
            
            TreeNode leftChild = current.left;
            TreeNode rightChild = current.right;
            
            if (leftChild == null && rightChild == null) {
                total += accumulated;
            } else {
                if (leftChild != null) {
                    nodeQueue.offer(leftChild);
                    valueQueue.offer(accumulated * 10 + leftChild.val);
                }
                if (rightChild != null) {
                    nodeQueue.offer(rightChild);
                    valueQueue.offer(accumulated * 10 + rightChild.val);
                }
            }
        }
        
        return total;
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes. Each node is processed exactly once.
• Space Complexity: O(n). Both queues hold at most n elements simultaneous.