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.Problem Overview: Each root-to-leaf path in a binary tree forms a number by concatenating node values. For example, the path 1 → 2 → 3 represents 123. The task is to traverse the tree, compute the number formed by every root-to-leaf path, and return the total sum.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
Use a recursive Depth-First Search to explore the tree from the root. Maintain the current number while traversing by multiplying the previous value by 10 and adding the current node's digit. When the traversal reaches a leaf node (both children are null), the accumulated value represents a complete root-to-leaf number, so add it to the total sum.
This approach works naturally with recursion because each call carries the partial number built along the path. The recursion depth equals the tree height, so the extra memory is proportional to O(h), where h is the height of the binary tree. Every node is visited exactly once, producing O(n) time complexity. This is the cleanest and most common solution used in interviews.
Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))
The same traversal can be implemented iteratively using an explicit stack. Store pairs of (node, currentNumber). Start with the root and value root.val. On each iteration, pop a node from the stack, update the number for its children using current * 10 + child.val, and push those children onto the stack.
When a popped node is a leaf, add the computed number to the running sum. The stack simulates the call stack used by recursion. At any time it stores nodes along the current DFS frontier, which keeps the extra memory bounded by the tree height. This method avoids recursion limits and is useful in environments where recursive depth may be constrained.
Recommended for interviews: Recursive DFS is the expected solution. It directly models the idea of building numbers along a path and results in concise code. Interviewers usually want to see that you recognize this as a tree traversal problem and propagate state through the recursion. The iterative stack version demonstrates deeper understanding of DFS mechanics and is helpful when discussing recursion alternatives.
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.
We use a helper function dfs that recursively computes the sum of the current path number while traversing the tree. If a leaf node is reached, it returns the current computed path sum. Otherwise, it recurses deeper into the tree.
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.
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.
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.
Time Complexity: O(n).
Space Complexity: O(n), due to the stack storing all nodes at least once.
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).
The calculation of the function dfs(root, s) is as follows:
root is null, return 0.s, i.e., s = s times 10 + root.val.s.dfs(root.left, s) + dfs(root.right, s).The time complexity is O(n), and the space complexity is O(log n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes, as it has to visit each node. |
| Iterative Depth-First Search (DFS) with Stack | Time Complexity: O(n). |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | Default interview solution for binary tree traversal problems |
| Iterative DFS with Stack | O(n) | O(h) | When avoiding recursion limits or implementing DFS manually |
Sum Root to Leaf Numbers - Coding Interview Question - Leetcode 129 • NeetCode • 42,507 views views
Watch 9 more video solutions →Practice Sum Root to Leaf Numbers with our built-in code editor and test cases.
Practice on FleetCode