Sum Root to Leaf Numbers

Given the root of a binary tree where each node contains a single digit, you need to calculate the sum of all root-to-leaf numbers. A root-to-leaf number is formed by concatenating the digits from the root to a leaf node. This problem is a classic example of tree traversal and demonstrates the importance of understanding recursive structures.

Problem Description

You are given the root of a binary tree. Each node in the tree contains an integer value between 0 and 9 (inclusive).

Your task is to calculate the total sum of all "root-to-leaf" numbers. A root-to-leaf path forms a number by concatenating the digits from the root down to a leaf.

For example, if a root-to-leaf path is 1 -> 2 -> 3, the number formed is 123.

Key Requirements:

• Traverse the binary tree to identify all root-to-leaf paths.
• For each path, construct the integer represented by concatenating the node values.
• Sum up all these constructed integers.

Expected Behavior:

The function should return a single integer representing the sum of all root-to-leaf numbers.

Edge Cases to Consider:

• An empty tree (root is null).
• A tree with only a root node.
• Trees where leaf nodes have different depths.

Examples

Example 1:

Input:
    1
   / \
  2   3

Output: 25
Explanation:
The root-to-leaf path `1 -> 2` forms the number 12.
The root-to-leaf path `1 -> 3` forms the number 13.
The total sum is 12 + 13 = 25.

Example 2:

Input:
    4
   / \
  9   0
 / \
5   1

Output: 1026
Explanation:
The root-to-leaf path `4 -> 9 -> 5` forms the number 495.
The root-to-leaf path `4 -> 9 -> 1` forms the number 491.
The root-to-leaf path `4 -> 0` forms the number 40.
The total sum is 495 + 491 + 40 = 1026.

Example 3: (Edge Case)

Input:
    7

Output: 7
Explanation:
The tree has only a root node, which is also a leaf. The number formed is 7.

Constraints

• The number of nodes in the tree is between 0 and 1000.
• Node values are integers between 0 and 9, inclusive.
• The maximum possible sum will fit within a standard integer type.

Notes

A common approach for this problem involves a recursive traversal (like Depth First Search - DFS). Think about how you can build the number as you traverse down the tree and how to handle the state (the current number being formed) across recursive calls. Remember that a leaf node is a node with no children.