Sum Root to Leaf Numbers
Understanding the Problem
We have a binary tree where each node holds a single digit (0-9). Every path from the root down to a leaf spells out a multi-digit number. Our job is to find the sum of all such numbers.
Take the tree [1,2,3]. The root is 1, with left child 2 and right child 3. The path 1->2 gives us the number 12 (not 1+2=3, but the concatenated digits treated as a decimal number). The path 1->3 gives us 13. The answer is 12 + 13 = 25.
The problem combines two subproblems: enumerate all root-to-leaf paths, and turn each path into a number. The first is standard tree traversal. The second comes down to one arithmetic fact: as we walk from root to leaf, each new digit shifts the previous number left by one decimal place and adds itself. If the running number so far is currentNum and the next node's value is val, the new number becomes currentNum * 10 + val. That is how we read numbers left to right, so we can build each path's number incrementally as we descend.
Key Constraints:
Number of nodes in [1, 1000]: The tree is never empty, so there is always at least one leaf and one path number to add. With at most 1000 nodes, a single O(n) traversal is fast enough.0 <= Node.val <= 9: Each node is a single digit, so the number along a path is the concatenation of those digits read top to bottom.Depth will not exceed 10: The longest path has at most 10 nodes, so a path number has at most 10 digits. A 10-digit value such as 9,999,999,999 overflows a 32-bitint, but the problem guarantees the total sum fits in a 32-bit int. Since every path number is non-negative, each one is at most the total sum, so each one also fits in a 32-bit int. A plainintaccumulator is therefore safe in every language here, and the depth bound of 10 keeps recursion shallow.
Approach 1: DFS with Path Collection
Intuition
One direct approach collects the digits along the current path, then converts that list into a number whenever we reach a leaf. We run a DFS that appends each node's value on the way down and removes it on the way back up, so the list always holds the path from the root to the node we are currently visiting.
This separates the two subproblems cleanly: the DFS handles path enumeration, and a small loop over the digit list handles number construction. It works, but it repeats work. At every leaf we re-scan the full path from scratch to rebuild a number that is mostly the same as its parent's number.
Algorithm
- Start a DFS from the root with an empty path list.
- At each node, append the node's value to the current path.
- If the node is a leaf (both children are null), iterate through the path digits to compute the number and add it to the running total.
- Recursively visit the left child and the right child.
- After visiting both children, remove the last element from the path (backtrack) so the path is clean for sibling exploration.
- Return the total sum.
Example Walkthrough
Input:
We trace the DFS, tracking path and totalSum:
- Visit root 1. Append it, so
path = [1]. Node 1 has children, so it is not a leaf. - Recurse left to node 2. Append it, so
path = [1, 2]. Node 2 has no children, so it is a leaf. Rebuild the number from the path:0, then0*10+1 = 1, then1*10+2 = 12. Add it, sototalSum = 12. Backtrack: remove 2, sopath = [1]. - Recurse right to node 3. Append it, so
path = [1, 3]. Node 3 is a leaf. Rebuild:0*10+1 = 1, then1*10+3 = 13. Add it, sototalSum = 12 + 13 = 25. Backtrack: remove 3, sopath = [1]. - Both children of node 1 are done. Backtrack: remove 1, so
path = []. The DFS finishes.
Code
- Time Complexity: O(n * h). We visit every node once during the DFS. At each leaf, we iterate through the entire path to compute the number, which takes O(h) where h is the tree height. For a balanced tree this is O(n log n), for a skewed tree O(n^2).
- Space Complexity: O(h). The path list holds at most h elements. The recursion stack also uses O(h) space. For a balanced tree h = O(log n), for a skewed tree h = O(n).
The repeated path-to-number conversion is the only inefficiency. When we move from a parent to a child, the number changes by one digit. The next approach removes the redundant work by passing the running number down as a parameter instead of rebuilding it at each leaf.
Approach 2: Recursive DFS with Running Number
Intuition
Instead of collecting paths and converting them at the leaves, we build the number as we descend. If the number formed by the path from the root down to a node's parent is currentNum, then the number at this node is currentNum * 10 + node.val. We carry that running value down through the recursion as a parameter.
This mirrors how a number is read left to right. Start with 0. Read a 4, and the number is 0*10+4 = 4. Read a 9, and it becomes 4*10+9 = 49. Read a 5, giving 49*10+5 = 495. When the recursion reaches a leaf, the parameter already holds the complete path number, so the leaf can return it directly. Each internal node returns the sum of what its two subtrees returned, so the total accumulates through the return values without any shared accumulator.
The reason we never need to know the path length in advance is that the multiply-by-10 step retroactively promotes every earlier digit. When a node at depth d along the path holds digit x, that digit later gets multiplied by 10 once for each remaining step down to the leaf. If the path continues for k more nodes, x ends up contributing x * 10^k, which is exactly its place value in the final number. Each digit therefore ends up in the correct decimal position no matter how far below it the leaf turns out to be.
Algorithm
- Define a recursive function
dfs(node, currentNum)that takes a node and the number formed so far. - If the node is null, return 0 (no contribution to the sum).
- Update the running number:
currentNum = currentNum * 10 + node.val. - If the node is a leaf (no children), return
currentNum. This path's number is complete. - Otherwise, return
dfs(left, currentNum) + dfs(right, currentNum)to sum contributions from both subtrees.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once, doing O(1) work at each node. No path iteration at the leaves.
- Space Complexity: O(h). The only space used is the recursion stack, which goes as deep as the tree height h. For a balanced tree h = O(log n), for a skewed tree h = O(n).
Approach 2 is optimal in time and uses only the recursion stack. The next approach replaces that recursion with an explicit stack, reaching the same O(n) time without relying on recursive calls. This is the form to use when deep recursion is a concern or when recursion is unavailable.
Approach 3: Iterative DFS with Stack
Intuition
We can convert the recursive approach to an iterative one using an explicit stack. The idea is identical: track the running number as we descend, and when we reach a leaf, add the completed number to the total. Instead of the system call stack holding our traversal state, we push (node, currentNum) pairs onto our own stack.
Algorithm
- Initialize a stack with the pair
(root, root.val). - Initialize
totalSum = 0. - While the stack is not empty:
- Pop a
(node, currentNum)pair. - If the node is a leaf, add
currentNumtototalSum. - If the node has a right child, push
(right, currentNum * 10 + right.val). - If the node has a left child, push
(left, currentNum * 10 + left.val). - Return
totalSum.
Example Walkthrough
We trace the tree [1, 2, 3]. Each stack entry pairs a node with the running number for the path ending at that node. Since the stack is LIFO, pushing the right child before the left child makes the left child come off the stack first, so the traversal visits the left subtree before the right. The push order only affects visit order, not the final sum, because every leaf's number is added regardless of when it is popped.
Code
- Time Complexity: O(n). Every node is pushed onto and popped from the stack exactly once. The work per node is O(1).
- Space Complexity: O(h). The stack holds at most O(h) entries at any time, where h is the height of the tree. For a balanced tree this is O(log n), for a skewed tree O(n).