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 the binary tree forms a number by concatenating node digits along the path. Your task is to compute the total sum of all such numbers. For example, a path 1 → 2 → 3 represents the number 123. Traverse every root-to-leaf path and accumulate the numeric value formed along the way.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
This approach uses recursion to traverse the tree using Depth-First Search. At each node, update the current number using current = current * 10 + node.val. When you reach a leaf node (both children are null), add the computed value to the total sum. The recursion naturally tracks the path from root to leaf, so each function call carries the partial number built so far. Since every node is visited exactly once, the time complexity is O(n) where n is the number of nodes. Space complexity is O(h) due to the recursion stack, where h is the tree height.
This method is clean and expressive for problems involving root-to-leaf paths in a tree. Most interview solutions follow this pattern because it maps directly to the problem’s recursive structure.
Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))
The same logic can be implemented iteratively using an explicit stack instead of recursion. Push pairs of (node, currentNumber) onto the stack. Each time you pop a node, compute the updated number using the same digit-building formula. If the node is a leaf, add the value to the running total. Otherwise, push its children along with the updated number.
This technique performs a manual DFS traversal of the binary tree. It avoids recursion depth limits and gives more control over the traversal order. The algorithm still visits each node once, so the time complexity remains O(n). The stack stores at most one path from root to leaf at a time, giving a space complexity of O(h).
Recommended for interviews: Recursive DFS is usually the expected solution. It clearly demonstrates understanding of tree traversal and path accumulation. Implementing the iterative stack version shows deeper mastery of DFS mechanics and is useful when recursion depth might become an issue. Interviewers typically look for the current * 10 + digit insight and a clean traversal that processes each root-to-leaf path exactly once.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(n), due to the stack storing all nodes at least once.
| 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). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Best general solution for tree traversal problems and most common interview approach |
| Iterative DFS with Stack | O(n) | O(h) | When avoiding recursion limits or when you want explicit control over traversal |
Sum Root to Leaf Numbers - Coding Interview Question - Leetcode 129 • NeetCode • 36,478 views views
Watch 9 more video solutions →Practice Sum Root to Leaf Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor