MediumTreeDepth-First SearchBinary Tree

Sum Root to Leaf Numbers

1 approach, code in every language

You are given the root of a binary tree in which every node holds a single digit between 0 and 9. Each root-to-leaf path spells out a number: read the digits from the root down to the leaf and concatenate them, so a path 1 -> 2 -> 3 represents the number 123.

Return the sum of all the numbers formed by the root-to-leaf paths. The problem guarantees the total fits within a 32-bit signed integer.

A leaf is a node with no children.

Example 1

Input: root = [1,2,3]

Output: 25

The path 1 -> 2 gives 12 and 1 -> 3 gives 13, so the total is 25.

Example 2

Input: root = [4,9,0,5,1]

Output: 1026

The paths spell 495, 491, and 40, which add up to 495 + 491 + 40 = 1026.

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.

DFS Carrying the Running Number

Push the partially built number down the tree with current = current * 10 + node.val, and add it to the total at each leaf.

Loading animation…

Intuition

Concatenating digits along a path is just building a base-10 number one digit at a time. Every time we step from a parent to a child we shift the accumulated value left by one digit (multiply by ten) and add the child's digit. When we reach a leaf, the accumulated value is exactly the number that path represents, so it contributes directly to the answer. Passing the running number down as a parameter means each node computes its contribution without any global bookkeeping. Summing the results from the left and right subtrees gives the total for the whole tree.

Algorithm walkthrough

1Define a DFS that receives the current node and the number built so far along the path from the root.
2If the node is null, it contributes nothing, so return 0.
3Update current = current * 10 + node.val to fold this node's digit into the running number.
4If the node is a leaf, return current because the path number is complete.
5Otherwise return the sum of the DFS results for the left and right children.
6Kick off the recursion with current = 0 at the root and return its result.

Implementation

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current: int) -> int:
            if not node:
                return 0
            current = current * 10 + node.val
            if not node.left and not node.right:
                return current
            return dfs(node.left, current) + dfs(node.right, current)

        return dfs(root, 0)

Time

O(n)

Space

O(h)

Each node is visited once. Extra space is the recursion stack, proportional to the tree height h (O(log n) if balanced, O(n) if skewed).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Total of the Menu Paths is our own problem on the technique behind Sum Root to Leaf Numbers: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free