Sum Root to Leaf Numbers

Problem

Each root-to-leaf path represents a number. Return the sum of all these numbers. Example: 1 → 2, 1 → 3 gives 12 + 13 = 25.

Key insight: DFS carrying current number; at leaf add to total.

Solutions

// C
int dfs(TreeNode* node, int cur) {
    if (!node) return 0;
    cur = cur * 10 + node->val;
    if (!node->left && !node->right) return cur;
    return dfs(node->left, cur) + dfs(node->right, cur);
}
int sumNumbers(TreeNode* root) { return dfs(root, 0); }

// C++
int dfs(TreeNode* node, int cur) {
    if (!node) return 0;
    cur = cur * 10 + node->val;
    if (!node->left && !node->right) return cur;
    return dfs(node->left, cur) + dfs(node->right, cur);
}
int sumNumbers(TreeNode* root) { return dfs(root, 0); }

// Java
public int sumNumbers(TreeNode root) {
    return dfs(root, 0);
}
int dfs(TreeNode node, int cur) {
    if (node == null) return 0;
    cur = cur * 10 + node.val;
    if (node.left == null && node.right == null) return cur;
    return dfs(node.left, cur) + dfs(node.right, cur);
}

// JavaScript
function sumNumbers(root) {
    function dfs(node, cur) {
        if (!node) return 0;
        cur = cur * 10 + node.val;
        if (!node.left && !node.right) return cur;
        return dfs(node.left, cur) + dfs(node.right, cur);
    }
    return dfs(root, 0);
}

# Python
def sumNumbers(root):
    def dfs(node, cur):
        if not node:
            return 0
        cur = cur * 10 + node.val
        if not node.left and not node.right:
            return cur
        return dfs(node.left, cur) + dfs(node.right, cur)
    return dfs(root, 0)

Complexity

Time: O(n)
Space: O(h)