How to Solve Sum Root to Leaf Numbers

The task is to sum all numbers formed from root to leaf paths in a binary tree. Using a depth-first search (DFS) approach, we track the numbers while traversing the tree. The problem is a good test for recursive traversal and state tracking in trees.

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

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.

How GhostInterview Helps

• Screenshot of the problem statement or tree visualization for better understanding.
• Step-by-step explanation of DFS approach, with clear breakdowns of how state tracking works.
• Walkthroughs of iterative and recursive methods, allowing you to compare both approaches during screen-share sessions.

Topic Pages

• Tree
• Depth-First Search
• Binary Tree

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.