Sum Root to Leaf Numbers
Problem
Given the root of a binary tree where each node contains a single digit, return the total sum of all root-to-leaf numbers formed by concatenating the digits along each path.
- The number of nodes in the tree is in the range [1, 1000]
- 0 ≤ Node.val ≤ 9
Example
root = [1,2,3]25There are two root-to-leaf paths: 1->2 and 1->3. These represent the numbers 12 and 13. Their sum is 12 + 13 = 25. The algorithm performs a DFS traversal, accumulating the current number by multiplying the previous accumulated value by 10 and adding the current node's digit. When a leaf node is reached, the accumulated number is returned. The sums from all leaf nodes are combined to produce the final result.
Approach
Straightforward Solution
A brute-force approach would generate all root-to-leaf paths as strings or lists, then convert each to an integer and sum them. This approach is inefficient due to extra space and conversions.
Core Observation
Each root-to-leaf path forms a number by concatenating digits, which can be computed incrementally by multiplying the accumulated value by 10 and adding the current node's digit. The problem reduces to summing these values over all leaf paths.
Path to Optimal
The key insight is to accumulate the numeric value during traversal, avoiding string or list construction. By passing the current accumulated number down the recursion, each node contributes to the number formation in O(1) time. When a leaf is reached, the accumulated number is returned and summed with other leaf results.
Optimal Approach
Use a DFS recursive function that takes the current node and the accumulated number so far. At each node, update the accumulated number by multiplying by 10 and adding the node's value. If the node is a leaf, return the accumulated number. Otherwise, recursively sum the results from left and right subtrees. This approach runs in O(n) time and O(h) space, where h is the tree height.
Time
O(n)
Each node is visited exactly once during the DFS traversal, and constant work is done per node.
Space
O(h)
The recursion stack depth is proportional to the height of the tree, which is O(h). No additional data structures proportional to n are used.
Pattern Spotlight
DFS (Stateful Exploration)
When a problem requires aggregating values along root-to-leaf paths, carry the partial state (like accumulated number) through recursive calls to avoid extra data structures and enable efficient computation.
Solution
| 1 | class Solution: |
| 2 | def sumNumbers(self, root: Optional[TreeNode]) -> int: |
| 3 | |
| 4 | def dfs(node, cur): |
| 5 | if not node: |
| 6 | return 0 |
| 7 | |
| 8 | cur = cur * 10 + node.val |
| 9 | |
| 10 | if not node.left and not node.right: |
| 11 | return cur |
| 12 | |
| 13 | return dfs(node.left, cur) + dfs(node.right, cur) |
| 14 | |
| 15 | return dfs(root, 0) |
Step-by-Step Solution
Accumulate Numeric Value Along Each Root-to-Leaf Path
| 4 | def dfs(node, cur): |
| 5 | if not node: |
| 6 | return 0 |
| 8 | cur = cur * 10 + node.val |
Objective
To recursively traverse the tree, updating the accumulated number by incorporating the current node's digit.
Key Insight
By multiplying the current accumulated number by 10 and adding the node's value, the algorithm simulates digit concatenation efficiently. This incremental approach avoids building explicit paths and leverages the numeric properties of decimal representation.
Interview Quick-Check
Core Logic
The DFS function carries the partial number formed so far, updating it at each node by shifting digits left (multiply by 10) and adding the current node's digit.
State & Boundaries
The base case returns 0 for null nodes, ensuring leaf checks are clean and preventing null pointer errors.
Common Pitfalls & Bugs
Forgetting to multiply the accumulated number by 10 before adding the current digit leads to incorrect number formation.
Return Accumulated Number at Leaf Nodes and Sum Subtree Results
| 10 | if not node.left and not node.right: |
| 11 | return cur |
| 13 | return dfs(node.left, cur) + dfs(node.right, cur) |
Objective
To identify leaf nodes and return the accumulated number, while summing results from left and right subtrees for internal nodes.
Key Insight
Leaf nodes represent complete root-to-leaf numbers, so their accumulated values are returned directly. Internal nodes combine the sums from their children, aggregating all root-to-leaf numbers in the subtree. This recursive summation ensures the final result is the total sum of all root-to-leaf numbers.
Interview Quick-Check
Core Logic
The function returns the accumulated number when a leaf node is reached, and otherwise returns the sum of recursive calls on left and right children.
State & Boundaries
Checking for leaf nodes by verifying absence of both left and right children ensures correct termination of each path.
Common Pitfalls & Bugs
Failing to return the accumulated number at leaf nodes or incorrectly summing subtree results leads to incorrect totals.
Initiate DFS Traversal from Root with Zero Accumulated Value
| 15 | return dfs(root, 0) |
Objective
To start the recursive DFS process from the root node with an initial accumulated number of zero.
Key Insight
Starting with zero ensures the first node's value is correctly incorporated without unintended scaling. This initial call sets the foundation for the entire traversal and accumulation process.
Interview Quick-Check
Core Logic
The initial call to dfs with the root and 0 starts the accumulation process correctly from the top of the tree.
State & Boundaries
Passing 0 as the initial accumulated value avoids incorrect number formation at the root.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
cur = cur * 10 + node.valUpdate the accumulated number by shifting digits left and adding current node's value.
Multiplying by 10 and adding the node's digit simulates concatenation of digits into a number efficiently during traversal.
return curReturn the accumulated number when a leaf node is reached.
At a leaf, the accumulated number represents a complete root-to-leaf number and must be included in the total sum.
if not node:Return 0 if the current node is null.
This base case prevents null pointer errors and contributes zero to the sum, effectively pruning invalid paths.
if not node.left and not node.right:Check if the current node is a leaf (no left or right children).
Identifying leaf nodes is critical because only complete root-to-leaf paths represent valid numbers to be summed.
return dfs(node.left, cur) + dfs(node.right, cur)Recursively sum the results from left and right subtrees.
Combining sums from both subtrees aggregates all root-to-leaf numbers in the current subtree, enabling a full traversal sum.
def dfs(node, cur):Define the recursive DFS helper function with current node and accumulated number.
Encapsulating the traversal and accumulation logic in a helper function allows passing the partial state (accumulated number) cleanly through recursion.
return 0Return 0 for null nodes to terminate recursion safely.
Ensures that leaf node checks and subtree sums handle missing children gracefully without additional checks.
return dfs(root, 0)Start DFS traversal from the root with initial accumulated value zero.
This call initializes the recursive process, ensuring the accumulation starts correctly from the root node.
Test Your Understanding
Why is it more efficient to accumulate the number during traversal rather than building paths as strings or lists?
Accumulating the number during traversal avoids the overhead of constructing and converting strings or lists for each path, reducing both time and space complexity by performing constant-time updates per node.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Sum Root to Leaf Numbers from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Sum Root to Leaf Numbers drill