129. Sum Root to Leaf Numbers - Detailed Explanation

Problem Statement

You are given the root of a binary tree where each node contains a single digit (0-9). Each path from the root down to a leaf forms a number by concatenating the digits along the path. For example, if a path is 1 -> 2 -> 3, it represents the number 123. The task is to find the sum of all these numbers for every root-to-leaf path in the tree. A leaf is a node with no children.

What to Return: Return an integer representing the total sum of all root-to-leaf numbers in the tree. (It is guaranteed that the sum will fit in a 32-bit integer.)

Constraints:

• The number of nodes in the tree is between 1 and 1000.
• Each node’s value is between 0 and 9 (inclusive).
• The maximum depth of the tree will not exceed 10 (so the longest root-to-leaf path has at most 10 digits, ensuring the numbers formed aren’t extremely large).

Example 1:
Input: root = [1,2,3]
This represents a tree:

    1
   / \
  2   3

Output: 25
Explanation: There are two root-to-leaf paths:

• Path 1->2 forms the number 12.
• Path 1->3 forms the number 13.
  Sum of these numbers = 12 + 13 = 25.

Example 2:
Input: root = [4,9,0,5,1]
This represents a tree:

      4
     / \
    9   0
   / \
  5   1

Output: 1026
Explanation: Root-to-leaf paths:

• Path 4->9->5 forms 495.
• Path 4->9->1 forms 491.
• Path 4->0 forms 40.
  Sum = 495 + 491 + 40 = 1026.

Example 3:
Input: root = [1,2,3,7,3,null,0,1,4,null,9,6,5]
This represents the tree:

          1
         / \
        2   3
       / \   \
      7   3   0
     / \   \  / \
    1   4   9 6  5

(Here null in the input list indicates an absent child.)
Output: 6395
Explanation: The root-to-leaf paths and their numbers are:

• 1 -> 2 -> 7 -> 1 = 1271
• 1 -> 2 -> 7 -> 4 = 1274
• 1 -> 2 -> 3 -> 9 = 1239
• 1 -> 3 -> 0 -> 6 = 1306
• 1 -> 3 -> 0 -> 5 = 1305
  Sum = 1271 + 1274 + 1239 + 1306 + 1305 = 6395.

Hints

• Hint 1: Consider how you form a number from digits. As you go down from the root to a child, you are essentially adding a new digit to the end of the current number. For example, going from 12 to a child with value 3 would form 123 (which is 12 * 10 + 3). This hint suggests that at each step, you might multiply the current accumulated value by 10 and then add the node’s value.

• Hint 2: Try exploring all root-to-leaf paths. A natural way is to traverse the tree. You can use Depth-First Search (DFS) or Breadth-First Search (BFS) to systematically visit all nodes. Think about how you can keep track of the number formed so far as you move deeper into the tree.

• Hint 3: Recursion can simplify the traversal. You could write a recursive function that carries the current number down to the children. When it hits a leaf, that current number is one complete root-to-leaf number to add to the total. This avoids having to store all path numbers separately.

• Hint 4: Don’t forget to handle edge cases: for example, a tree with only one node should just return that node’s value. If a node has one child (only left or only right), your logic should still correctly propagate the current number down that single path.

Approach Explanation

There are multiple ways to solve this problem. The goal for each approach is to traverse the tree and accumulate the numeric values of each root-to-leaf path. Here, we will discuss three approaches: (1) Depth-First Search using recursion, (2) Depth-First Search using an explicit stack (iterative), and (3) Breadth-First Search using a queue (iterative). All approaches ultimately do the same computations but in slightly different ways.

1. Depth-First Search (DFS) – Recursive Approach

Idea: Use recursion (a form of DFS) to explore each path from the root to leaves, while building the number represented by the path. Pass along the current accumulated number to children. When a leaf is reached, the accumulated number is one complete root-to-leaf number, which we add to a global or outer sum.

How it works step-by-step:

1. Start at the root: Call a recursive function with the root node and an initial current sum of 0.
2. Process the current node: Update the current sum by incorporating the node’s value. Since moving down a level adds a digit, do:
   currentSum = currentSum * 10 + node.val.
   For example, if currentSum was 12 and node.val is 3, new currentSum becomes 123.
3. Check leaf node: If the current node is a leaf (no left or right child), this currentSum is a complete number from root to leaf. Add this value to a global result (or use a return value to propagate it up).
4. Recur on children: If the node is not a leaf, recursively call the function on the left child with the updated currentSum, and on the right child with the updated currentSum. Sum the results from the left and right subtrees.
5. Return sum up the call stack: Each recursive call returns the total sum of numbers from that subtree. The root call will return the final sum of all paths.

Example Walk-through (Recursive DFS): Using Example 2 (tree: 4 -> 9,0 -> ...):

• Start at root (4) with currentSum = 0.
• At node 4: currentSum = 0*10 + 4 = 4. Not a leaf, so traverse children.
  • Go left to node 9 with currentSum = 4.
  • At node 9: currentSum = 4*10 + 9 = 49. Not a leaf.
    • Go left to node 5 with currentSum = 49.
    • At node 5: currentSum = 49*10 + 5 = 495. Node 5 is a leaf, so return 495.
    • Go right to node 1 with currentSum = 49.
    • At node 1: currentSum = 49*10 + 1 = 491. Node 1 is a leaf, return 491.
    • Node 9 returns sum = 495 + 491 = 986 (sum of left and right paths under 9).
  • Go right to node 0 with currentSum = 4.
  • At node 0: currentSum = 4*10 + 0 = 40. Node 0 is a leaf, return 40.
  • Node 4 (root) collects sum = left subtree (986) + right subtree (40) = 1026.
• The recursion ends, and the result returned is 1026.

Key points:

• We carry along the current number as we go deeper.
• When we hit a leaf, we have a complete number to add.
• Recursion naturally backtracks, so we don’t need to explicitly remove the last digit; each recursive call has its own copy of current sum value.

2. Depth-First Search (DFS) – Iterative using a Stack

Idea: This approach does the same DFS traversal but uses an explicit stack instead of recursion. We will push nodes onto a stack, along with the number formed so far on the path to that node. This is useful in languages or situations where deep recursion might be a concern.

How it works:

1. Use a stack to simulate the DFS. Initialize it with the root node and its value (or root and initial sum 0).
2. While the stack is not empty:
   • Pop the top element (this gives a node and the current number formed up to that node).
   • If this node is a leaf, add the current number to a running total sum.
   • If not a leaf, push its children onto the stack:
     • If the node has a right child, push the right child and the updated number current*10 + right.val.
     • If the node has a left child, push the left child and the updated number current*10 + left.val. (We push right child first so that left child is processed first – this maintains the typical DFS order where left side is done before right, although order doesn't affect the final sum.)
3. Continue until stack is empty. The running total will then contain the sum of all root-to-leaf numbers.

Example Walk-through (Iterative DFS with Stack): Using Example 1 ([1,2,3]):

• Initialize stack with (node=1, currentNum=1). Total sum = 0.
• Pop (1,1). Node 1 is not leaf.
  • Push its right child: push (3, currentNum=1*10+3 = 13).
  • Push its left child: push (2, currentNum=1*10+2 = 12).
• Pop top -> (2,12). Node 2 is a leaf? Node 2 has no children in this example? (Actually in [1,2,3], 2 is a leaf, yes it has no children in that tree).
  • Node 2 is a leaf, add 12 to sum. Total sum = 12.
• Pop next -> (3,13). Node 3 is a leaf, add 13 to sum. Total sum = 12 + 13 = 25.
• Stack empty, result = 25.

(If the node had children, we would push them. The process ensures we visit all paths.)

Key points:

• The stack holds pairs of (node, currentNumber).
• This method explicitly manages the traversal stack instead of using the call stack.
• It achieves the same result as recursion, and the order of traversal (preorder-like) ensures each path’s number is computed correctly.

3. Breadth-First Search (BFS) – Iterative using a Queue

Idea: BFS traverses the tree level by level. We can also compute the path sums using BFS by carrying the current number with each node in a queue. BFS is not the most typical approach for this problem, but it works just as well.

How it works:

1. Use a queue to perform level-order traversal. Enqueue the root node with its value as the current number.
2. While the queue is not empty:
   • Dequeue an element (node, currentNumber).
   • If the node is a leaf, add currentNumber to a total sum.
   • If the node has a left child, enqueue (leftChild, currentNumber*10 + leftChild.val).
   • If the node has a right child, enqueue (rightChild, currentNumber*10 + rightChild.val).
3. Continue until the queue is empty. The total sum will be the answer.

Example Walk-through (BFS): Using Example 1 ([1,2,3]):

• Enqueue (1,1). Total sum = 0.
• Dequeue (1,1). Not a leaf.
  • Enqueue (2, 12) and (3, 13) [(2 from left, 3 from right)].
• Dequeue (2,12). Node 2 is a leaf, add 12 to sum (sum=12). Node 2 has no children to enqueue.
• Dequeue (3,13). Node 3 is a leaf, add 13 to sum (sum=25). Node 3 has no children.
• Queue empty, result = 25.

For a larger tree, BFS will process all nodes level by level, but still accumulates path values correctly before adding to sum at leaves.

Key points:

• BFS uses a queue and can be useful if you want to naturally handle trees level by level.
• Order of traversal (level-order) doesn’t affect the final sum calculation.
• You still carry the current number similarly as in DFS.

Choosing an Approach:

All three approaches will yield the correct result. The recursive DFS is often the simplest to implement and reason about for this problem. The iterative DFS (stack) is conceptually similar to recursion but avoids potential recursion depth issues. The BFS (queue) approach is less common for this particular problem but is a valid alternative.

Code Implementation