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.
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 path1->2represents the number12. The root-to-leaf path1->3represents the number13. Therefore, sum = 12 + 13 =25.
Example 2:
Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path4->9->5represents the number 495. The root-to-leaf path4->9->1represents the number 491. The root-to-leaf path4->0represents the number 40. Therefore, sum = 495 + 491 + 40 =1026.
Constraints:
[1, 1000].0 <= Node.val <= 910.In #129 Sum Root to Leaf Numbers, each root-to-leaf path in a binary tree forms a number by concatenating node values along the path. The goal is to compute the sum of all such numbers. A common way to approach this is by using Depth-First Search (DFS) to explore every root-to-leaf path.
During traversal, maintain a running value that represents the number formed so far. At each node, update this value using current = current * 10 + node.val. When a leaf node is reached, add the accumulated value to the total sum. This ensures each path contributes exactly one number.
Both recursive DFS and iterative DFS using a stack can solve the problem efficiently. The algorithm visits each node exactly once while carrying the partial number along the traversal path. This makes the approach efficient and well-suited for typical binary tree constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive DFS | O(n) | O(h) |
| Iterative DFS (Stack) | O(n) | O(h) |
NeetCode
This approach makes use of recursive DFS to traverse from the root to all leaf nodes while maintaining the path number formed by the nodes on the path. At each step, multiply the current number by 10 and add the node's value to propagate the root-to-leaf number down the path. When a leaf node is reached, add the path number to an overall sum.
Time Complexity: O(n), where n is the number of nodes, as it has to visit each node.
Space Complexity: O(h), where h is the height of the tree due to recursive call stack.
1class Solution:
2 def sumNumbers(self, root: TreeNode) -> int:
3 def dfs(node, current_sum):
4 ifThe Python solution utilizes the nested function dfs which traverses the binary tree and calculates the path sums for all root-to-leaf paths using a recursive approach.
This approach uses an iterative DFS with a stack to avoid deep recursive calls. Here, we use a stack to simulate the call stack and iterate through the nodes. Each entry in the stack contains the node and the path sum up to that node, allowing us to process nodes on the path to construct the full number.
Time Complexity: O(n).
Space Complexity: O(n), due to the stack storing all nodes at least once.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
DFS is ideal because the problem requires exploring complete root-to-leaf paths. It allows you to carry a running numeric value along the path and process it only when a leaf node is reached.
Yes, variations of this problem frequently appear in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of tree traversal, recursion, and how to propagate values during DFS.
A binary tree traversal using recursion or an explicit stack works best. DFS naturally follows root-to-leaf paths, making it easy to maintain the number formed along the path while exploring the tree.
The optimal approach is Depth-First Search (DFS). While traversing the tree, you build the number for each path by multiplying the previous value by 10 and adding the current node value. When a leaf node is reached, the accumulated number is added to the final sum.
This C solution uses a manually managed stack to simulate the DFS traversal. Each element in the stack stores the current node and the sum formed up to that node. The approach emulates the process of recursion iteratively.