Sum Root to Leaf Numbers - Video Solutions
Sum Root to Leaf Numbers - Coding Interview Question - Leetcode 129
Sum Root to Leaf Numbers - Video Solution
Watch 10 video solutions for Sum Root to Leaf Numbers, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by NeetCode has 43,596 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
- For example, the root-to-leaf path
1 -> 2 -> 3represents the number123.
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:
- 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.
Approach Overview
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.
Complexity Analysis
| 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 |