Sum Root to Leaf Numbers - Video Solutions

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.