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 Sam K., 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

More Trees practice problems

See all Trees problems →