Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(node, current):
            if not node:
                return 0
            current = current * 10 + node.val
            if not node.left and not node.right:
                return current
            return dfs(node.left, current) + dfs(node.right, current)
        return dfs(root, 0)
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    
    int dfs(TreeNode* node, int current) {
        if (!node) return 0;
        current = current * 10 + node->val;
        if (!node->left && !node->right) return current;
        return dfs(node->left, current) + dfs(node->right, current);
    }
};
      

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

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int current) {
        if (node == null) return 0;
        current = current * 10 + node.val;
        if (node.left == null && node.right == null) return current;
        return dfs(node.left, current) + dfs(node.right, current);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    function dfs(node, current) {
        if (!node) return 0;
        current = current * 10 + node.val;
        if (!node.left && !node.right) return current;
        return dfs(node.left, current) + dfs(node.right, current);
    }
    return dfs(root, 0);
};
      

Problem Description

Given a binary tree where each node contains a single digit (from 0 to 9), each root-to-leaf path represents a number formed by concatenating the digits along the path. The task is to find the total sum of all such numbers formed from root to leaf paths in the tree.

For example, if a path from root to leaf is 1 -> 2 -> 3, it represents the number 123. You must sum all such numbers for every root-to-leaf path.

• There may be multiple root-to-leaf paths.
• Each node's value is a single digit (0-9).
• The tree is non-empty.

Thought Process

To solve this problem, we need to explore all paths from the root to every leaf in the binary tree. For each path, we construct a number by concatenating the digits we encounter. At every leaf node, we add the resulting number to our total sum.

A brute-force way would be to generate all possible paths as lists, convert each to a number, and sum them up. However, this can be optimized by building the number as we traverse the tree, passing the current value down to child nodes. This avoids extra space and repeated computation.

The key insight is to use depth-first search (DFS), carrying the "current number so far" as we go deeper, and only adding to the sum when we reach a leaf node.

Solution Approach

The elegant solution uses recursion and DFS. Here’s how it works step by step:

1. Start at the root node with an initial number of 0.
2. At each node, update the current number by multiplying the existing number by 10 and adding the node's digit value. This mimics "appending" the digit.
3. If the node is a leaf (both children are null), return the current number. This number represents one complete root-to-leaf path.
4. If the node is not a leaf, recurse down the left and right children, passing the updated current number.
5. Sum up the results from the left and right subtrees. This accumulates all root-to-leaf numbers.
6. Return the final sum after the recursion completes.

This approach is efficient because:

• It avoids storing all paths explicitly.
• Each node is visited only once.
• The current number is built incrementally as we go deeper.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
  

Step-by-step traversal:

1. Start at root 1, current number is 1.
2. Go left to 2: current number becomes 1 * 10 + 2 = 12. Node 2 is a leaf, so add 12 to sum.
3. Go right to 3: current number becomes 1 * 10 + 3 = 13. Node 3 is a leaf, so add 13 to sum.
4. Total sum is 12 + 13 = 25.

The process recursively builds each number as it descends, and only adds to the sum at leaf nodes.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(NL), where N is the number of nodes and L is the maximum path length (since you might store each path).
  • Space Complexity: O(NL) for storing all root-to-leaf paths.
• Optimized DFS approach (as above):
  • Time Complexity: O(N) because each node is visited once.
  • Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

This makes the DFS solution both time and space efficient.

Summary

The key to solving the Sum Root to Leaf Numbers problem is recognizing that you can build each number incrementally as you traverse the tree, and only need to sum the numbers at the leaves. By using a simple DFS recursion, you avoid unnecessary storage and repeated computation, resulting in an elegant and efficient solution that is easy to implement in any language.