Is Sum Root to Leaf Numbers easy or hard?

Sum Root to Leaf Numbers is considered a medium-level problem. The tree traversal itself is straightforward, but candidates must recognize how to build numbers incrementally along each path and detect leaf nodes correctly.

Sum Root to Leaf Numbers Python/Java solution

Python and Java solutions both implement DFS. Pass the current path number as a parameter during recursion, update it with current * 10 + node.val, and add it to the result when a leaf is reached. The logic is identical across languages with O(n) time complexity.

How to solve Sum Root to Leaf Numbers in O(n)?

Perform a DFS traversal from the root while maintaining a running number. At each step compute currentNumber = previousNumber * 10 + node.val. When reaching a leaf node, add this number to the total sum. Since the algorithm touches each node once, the total runtime stays O(n).

What is the best approach for Sum Root to Leaf Numbers?

Depth-First Search (DFS) is the best approach. Traverse the binary tree while carrying the number formed so far, updating it as current * 10 + node.val. When a leaf node is reached, add the accumulated value to the total sum. This processes each node once, giving O(n) time complexity.

Is Sum Root to Leaf Numbers asked at Google/Amazon/Meta?

Tree traversal problems similar to Sum Root to Leaf Numbers appear frequently in interviews at companies like Amazon, Google, and Meta. They test understanding of DFS, recursion, and passing state along tree paths. Variations often involve computing values along root-to-leaf paths.

What data structure is used in Sum Root to Leaf Numbers?

The main data structure is a binary tree. The algorithm uses depth-first traversal implemented either through recursion (implicit call stack) or an explicit stack. Both methods track the current numeric value along each path.

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

The time complexity is O(n) because every node in the binary tree is visited exactly once during the traversal. Each visit performs constant work to update the path number and check whether the node is a leaf. Space complexity is O(h), where h is the height of the tree due to recursion or the DFS stack.

Description Solution Video 5:42

129. Sum Root to Leaf Numbers

Medium70.3% acceptance7 companies

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. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

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.

Constraints: