Sum Root to Leaf Numbers - Video Solutions

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.