Skip to main content

129. Sum Root to Leaf Numbers

medium

Each root-to-leaf path represents a digit-by-digit decimal number. Sum them all. The trick is folding the running number into the recursion — current * 10 + node.val — instead of building strings.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given the root of a binary tree containing digits from 0 to 9 only. Each root-to-leaf path in the tree represents a number. For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123. Return the total sum of all root-to-leaf numbers.

Constraints

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

Examples

Example 1

Input
root = [1,2,3]
Output
25

Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25.

Example 2

Input
root = [4,9,0,5,1]
Output
1026

Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Building strings and parsing at leaves works but wastes effort. Carry the running number numerically.

Hint 2

When you step from parent to child, the new running value is parent * 10 + child.val.

Hint 3

At a leaf, return the running value. At a null child, return 0 (so internal nodes with one child don't double-count).

Solution approach

Reveal approach

Recursive DFS carrying the path number. Helper dfs(node, current): if node is null return 0. Compute current = current * 10 + node.val. If node is a leaf (no children), return current. Otherwise return dfs(node.left, current) + dfs(node.right, current). Top-level call: dfs(root, 0). The base case 'null returns 0' is important because a node with only one child shouldn't be treated as a leaf — its null child must contribute 0, not the partial running value. O(n) time, O(h) recursion space.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • tree-dfs
  • recursion
  • backtracking

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Sum Root to Leaf Numbers and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →