Sum Root to Leaf Numbers — LC 129 FAANG Tree DFS Pattern

Problem Statement#

You are given the root of a binary tree containing digits from 0 to 9 only. Each root-to-leaf path represents a number formed by concatenating the digits along the path. Return the total sum of all root-to-leaf numbers. The answer is guaranteed to fit in a 32-bit integer.

Constraints:

• The number of nodes is in the range [1, 1000]
• 0 <= Node.val <= 9
• The depth of the tree will not exceed 10

Input:  root = [1,2,3]
Output: 25
        Path 1->2 = 12, path 1->3 = 13, sum = 25

Input:  root = [4,9,0,5,1]
Output: 1026
        Paths: 495, 491, 40 -> 495 + 491 + 40 = 1026

Why This Problem Matters#

LeetCode 129 Sum Root to Leaf Numbers is a staple binary tree interview question asked at Meta, Amazon, Google, Microsoft, and Bloomberg. It is one of the cleanest examples of the carry-state DFS pattern: you push partial information down the tree and finalize it at leaves. Recruiters love it because a strong candidate solves it in under five minutes with optimal complexity, while weaker candidates over-engineer with explicit path lists.

This is also a frequent warm-up problem in Meta phone screens and Amazon onsite loops. The same pattern reappears in LC 257 Binary Tree Paths, LC 113 Path Sum II, and LC 988 Smallest String Starting From Leaf, so mastering this template pays compound interest across FAANG tree problems.

Beyond interviews, the technique generalizes to any tree-structured accumulation: building file paths, computing inherited permissions, propagating taint analysis in compilers, and evaluating expression trees.

The Core Insight#

Each digit at depth d contributes 10^(depth - d) to the path number. Instead of computing this exponent, we exploit positional shift: a number 12 followed by digit 3 becomes 123 = 12 * 10 + 3. So as we descend, we maintain a running number cur = cur * 10 + node.val.

When we reach a leaf, cur is the complete root-to-leaf number — add it to the running total. For internal nodes, recurse left and right with the updated cur and sum their results. Because cur is a primitive integer passed by value, each recursive branch sees its own copy — no need to backtrack or undo state.

This converts an O(n * h) brute force (build full path then convert) into a single O(n) DFS with O(h) call-stack memory.

Visual Dry Run#

Tree: [4, 9, 0, 5, 1]

        4
       / \
      9   0
     / \
    5   1

Total = 495 + 491 + 40 = 1026.

Solution (Optimal)#

class Solution:
    def sumNumbers(self, root) -> int:
        def dfs(node, cur):
            if not node:
                return 0
            cur = cur * 10 + node.val
            # Leaf: this path's number is finalized
            if not node.left and not node.right:
                return cur
            # Internal: sum contributions from both subtrees
            return dfs(node.left, cur) + dfs(node.right, cur)
 
        return dfs(root, 0)

var sumNumbers = function(root) {
    const dfs = (node, cur) => {
        if (!node) return 0;
        cur = cur * 10 + node.val;
        if (!node.left && !node.right) return cur;
        return dfs(node.left, cur) + dfs(node.right, cur);
    };
    return dfs(root, 0);
};

Time: O(n) — every node is visited exactly once. Space: O(h) — recursion stack proportional to tree height; O(log n) balanced, O(n) worst case.

Common Mistakes#

• Adding cur at every node instead of only at leaves — internal nodes are not paths.
• Treating a node with only one child as a leaf. A leaf has BOTH children null.
• Building string paths and parsing with int(...) — works but is wasteful and error-prone.
• Forgetting the empty tree case (root is None should return 0).
• Mutating a shared list across branches without backtracking — corrupts other paths.

Interview Tips#

• Clarify: "Are values always single digits 0-9?" Confirms the * 10 trick is safe.
• Draw a small tree like [1,2,3] and verbally walk through cur updates before coding.
• State complexity up front: "O(n) time, O(h) space, single DFS pass."
• Mention the alternative (collect paths as strings) and explain why running integer is better.
• If the interviewer pushes on iterative, offer a stack-based approach with (node, cur) tuples.

Follow-up Questions#

• Iterative version? Use an explicit stack of (node, cur) pairs. Same O(n) time, O(h) space.
• Print all paths instead of summing? Pass a list, append on entry, pop on exit (backtracking).
• What if values can be multi-digit? Replace cur * 10 with cur * 10^digits(node.val).
• Binary digits version (LC 1022)? Same pattern with cur * 2 + node.val.
• Largest root-to-leaf number? Track max instead of sum at leaves.

Key Takeaways#

• LeetCode 129 is a Medium-difficulty FAANG tree DFS question asked at Meta, Amazon, and Google.
• The optimal pattern is carry-and-accumulate DFS: cur = cur * 10 + node.val pushed down by value.
• Time complexity is O(n), space complexity is O(h) where h is tree height.
• A leaf is defined as a node where both left and right are null — checking only one is a bug.
• The pattern generalizes to LC 257, LC 113, LC 988, and LC 1022 binary path problems.
• Passing cur by value automatically handles backtracking — no manual undo needed.
• This is a 5-minute warm-up at FAANG; over-engineering signals weak intuition.