How do you solve Sum Root to Leaf Numbers?

Use a DFS recursive function that takes the current node and the accumulated number so far. At each node, update the accumulated number by multiplying by 10 and adding the node's value. If the node is a leaf, return the accumulated number. Otherwise, recursively sum the results from left and right subtrees. This approach runs in O(n) time and O(h) space, where h is the tree height.

What pattern does Sum Root to Leaf Numbers use?

The Pattern: DFS (Stateful Exploration) The Heuristic: When a problem requires aggregating values along root-to-leaf paths, carry the partial state (like accumulated number) through recursive calls to avoid extra data structures and enable efficient computation.

Sum Root to Leaf Numbers — DFS

Q: What is the time complexity of Sum Root to Leaf Numbers?

O(n). Each node is visited exactly once during the DFS traversal, and constant work is done per node.

Problem

Given the root of a binary tree where each node contains a single digit, return the total sum of all root-to-leaf numbers formed by concatenating the digits along each path.

The number of nodes in the tree is in the range [1, 1000]
0 ≤ Node.val ≤ 9

Example

Input: root = [1,2,3]

Output: 25

There are two root-to-leaf paths: 1->2 and 1->3. These represent the numbers 12 and 13. Their sum is 12 + 13 = 25. The algorithm performs a DFS traversal, accumulating the current number by multiplying the previous accumulated value by 10 and adding the current node's digit. When a leaf node is reached, the accumulated number is returned. The sums from all leaf nodes are combined to produce the final result.

Approach

Straightforward Solution

A brute-force approach would generate all root-to-leaf paths as strings or lists, then convert each to an integer and sum them. This approach is inefficient due to extra space and conversions.

Core Observation

Each root-to-leaf path forms a number by concatenating digits, which can be computed incrementally by multiplying the accumulated value by 10 and adding the current node's digit. The problem reduces to summing these values over all leaf paths.

Path to Optimal

Preview

The key insight is to accumulate the numeric value during traversal, avoiding string or list construction. By passing the current accumulated number down the recursion, each node contributes to the number formation in O(1) time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a DFS recursive function that takes the current node and the accumulated number so far. At each node, update the accumulated number by multiplying by 10 and adding the node's value…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited exactly once during the DFS traversal, and constant work is done per node.

Space

O(h)

The recursion stack depth is proportional to the height of the tree, which is O(h). No additional data structures proportional to n are used.

Solution

Python

1class Solution:
2    def sumNumbers(self, root: Optional[TreeNode]) -> int:
3
4        def dfs(node, cur):
5            if not node:
6                return 0
7
8            cur = cur * 10 + node.val
9
10            if not node.left and not node.right:
11                return cur
12
13            return dfs(node.left, cur) + dfs(node.right, cur)
14
15        return dfs(root, 0)

Step-by-Step Solution

1

Accumulate Numeric Value Along Each Root-to-Leaf Path

4def dfs(node, cur):
  if not node:
      return 0
  cur = cur * 10 + node.val

Objective

To recursively traverse the tree, updating the accumulated number by incorporating the current node's digit.

Key Insight

By multiplying the current accumulated number by 10 and adding the node's value, the algorithm simulates digit concatenation efficiently. This incremental approach avoids building explicit paths and leverages the numeric properties of decimal representation.

Interview Quick-Check

Core Logic

The DFS function carries the partial number formed so far, updating it at each node by shifting digits left (multiply by 10) and adding the current node's digit.

State & Boundaries

The base case returns 0 for null nodes, ensuring leaf checks are clean and preventing null pointer errors.

Common Pitfalls & Bugs

Forgetting to multiply the accumulated number by 10 before adding the current digit leads to incorrect number formation.

2

Return Accumulated Number at Leaf Nodes and Sum Subtree Results

To identify leaf nodes and return the accumulated number, while summing results from left and right subtrees for internal nodes.

3

Initiate DFS Traversal from Root with Zero Accumulated Value

To start the recursive DFS process from the root node with an initial accumulated number of zero.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

cur = cur * 10 + node.val

Update the accumulated number by shifting digits left and adding current node's value.

Multiplying by 10 and adding the node's digit simulates concatenation of digits into a number efficiently during traversal.

Line 11 Critical

return cur

Return the accumulated number when a leaf node is reached.

At a leaf, the accumulated number represents a complete root-to-leaf number and must be included in the total sum.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why is it more efficient to accumulate the number during traversal rather than building paths as strings or lists?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sum Root to Leaf Numbers from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sum Root to Leaf Numbers drill

or drill a free problem

1	`class Solution:`
2	`def sumNumbers(self, root: Optional[TreeNode]) -> int:`
3
4	`def dfs(node, cur):`
5	`if not node:`
6	`return 0`
7
8	`cur = cur * 10 + node.val`
9
10	`if not node.left and not node.right:`
11	`return cur`
12
13	`return dfs(node.left, cur) + dfs(node.right, cur)`
14
15	`return dfs(root, 0)`

4	`def dfs(node, cur):`
5	`if not node:`
6	`return 0`
8	`cur = cur * 10 + node.val`