#129

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Sum Root to Leaf Numbers

Calculate the sum of all root-to-leaf numbers in a binary tree where each path represents a number.

Problem Statement

You are given the root of a binary tree containing digits from 0 to 9 only. Each path from the root to a leaf node represents a number, where each node's value is a digit in that number. The task is to return the sum of all numbers formed by these root-to-leaf paths.

The binary tree contains at least one node, and the number of nodes in the tree is between 1 and 1000. The value of each node is between 0 and 9. Additionally, the tree depth does not exceed 10. The answer will fit within a 32-bit integer.

Examples

Example 1

Input: root = [1,2,3]

Output: 25

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

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

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.

Solution Approach

Binary-Tree Traversal and State Tracking

The problem requires a traversal of the binary tree. A Depth-First Search (DFS) approach is ideal to explore all root-to-leaf paths. As you traverse, maintain a running number formed by concatenating the values of the nodes from the root to the current node. When reaching a leaf node, add the number to the final sum. This allows efficient tracking of the total sum of all root-to-leaf numbers.

Recursive DFS Implementation

Using recursion, we can simulate the DFS traversal by passing down the current number as we move from one node to the next. At each node, we multiply the current number by 10 and add the current node's value. Once a leaf node is reached, the accumulated number is added to the sum. The base case of the recursion will trigger when a leaf node is encountered.

Iterative DFS Using a Stack

Alternatively, an iterative DFS approach can be used with an explicit stack. In this approach, we maintain a stack to track the current path and number as we traverse. Each stack entry will include a node and the number formed up to that point. This approach can sometimes offer more control, especially in iterative or non-recursive environments.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree, since we visit each node once. The space complexity is O(H), where H is the height of the tree. In the worst case, this can be O(N) for a skewed tree, but typically, the space complexity will be proportional to the height of the tree, which is capped at 10 according to the problem's constraints.

What Interviewers Usually Probe

Do you understand how DFS is applied to track root-to-leaf paths?
Can you explain how you would modify your approach if the tree had more complex node values?
Are you able to handle edge cases where the tree has only one node?

Common Pitfalls or Variants

Common pitfalls

Not properly tracking the current number as you traverse the tree, leading to incorrect sums.
Forgetting to add the number formed at the leaf node to the final sum.
Confusing binary-tree traversal approaches, such as mixing up DFS with BFS, or not accounting for recursion depth.

Follow-up variants

Sum of all paths that lead to the leaf nodes of a n-ary tree.
Calculate the product instead of the sum of root-to-leaf numbers in a binary tree.
Find the maximum root-to-leaf number formed in a binary tree.

FAQ

How do you handle leaf nodes in this problem?

When you reach a leaf node, you add the number formed by the current root-to-leaf path to the sum. This ensures that only complete paths contribute to the result.

What happens if the tree only has one node?

If the tree only contains one node, that node itself represents the sum. Since there are no other paths, the result will be just the value of that node.

What traversal pattern is best for this problem?

A depth-first search (DFS) traversal works best because it allows you to track the state (number formed) as you go down each path from root to leaf.

How does the recursive approach handle state tracking?

The recursive approach passes down the current number being formed at each step. When a leaf node is reached, the accumulated number is added to the total sum.

How would the complexity change if the tree had more than 1000 nodes?

If the tree had more than 1000 nodes, the time complexity would still be O(N), where N is the number of nodes. However, deeper trees may impact space complexity due to the increased recursion stack or iterative stack size.

terminal

Solution

Solution 1: DFS

We can design a function $dfs(root, s)$, which represents the sum of all path numbers from the current node $root$ to the leaf nodes, given that the current path number is $s$. The answer is $dfs(root, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, s):
            if root is None:
                return 0
            s = s * 10 + root.val
            if root.left is None and root.right is None:
                return s
            return dfs(root.left, s) + dfs(root.right, s)

        return dfs(root, 0)

Continue Practicing

#124 binary tree maximum path sum #117 populating next right pointers in each node ii #116 populating next right pointers in each node