The O(n) Club: Sum Root to Leaf Numbers: Why Trees Love Place Value (LeetCode 129)

The O(n) Club: Sum Root to Leaf Numbers—Why Trees Love Place Value (LeetCode 129)

⚡ TL;DR

Take a binary tree stuffed with digits (0–9). Walk from the root to each leaf, building a big number as you go—no, not by just adding nodes, but by growing a real integer (place value matters, folks). Sum all the final numbers. Brute force? StringBuilder and Integer.parseInt at every turn. But let Java’s arithmetic tag in:

// Classic recursion, Java-style
public int sumNumbers(TreeNode root) {
    return helper(root, 0);
}
private int helper(TreeNode node, int acc) {
    if (node == null) return 0;
    int next = acc * 10 + node.val;
    if (node.left == null && node.right == null) return next;
    return helper(node.left, next) + helper(node.right, next);
}

🧠 How Devs Usually Mess This Up

So many slip on the banana peel of place value: they just do 1+2+3 (which, congrats, is 6), instead of producing 123 (which, surprise, is 123). Others think any node with only one child is a leaf. If you’re not sure whether a node is a leaf, the answer is: absolutely no children allowed. And don’t forget to reset your number accumulator down each path—otherwise you’ll get (almost) the right answer in a parallel universe.

🔍 What’s Actually Going On

Pretend you’re a robot chef stacking ingredients into a blender: every choice is a digit tossed in at a higher place value—shake, don’t stir! You travel from the binary root to every terminal node, building up the ‘dish’ (number) by moving the previous sum one decimal to the left and adding the new digit. When you reach a leaf, serve that dish, and when all dishes are served, your ‘meal’ is the sum.

🛠️ PseudoCode

• Start from the root with your accumulator at 0.
• At each node:
  • Update: current = accumulator * 10 + node.val
  • If leaf (left == null && right == null): return current
  • Otherwise, recurse left and right, summing the results.
• Iterative? Use a stack of (node, valueSoFar) and process like a 90s pizza delivery route.

// Java-ish DFS
int total = 0;
void dfs(TreeNode node, int curr) {
    if (node == null) return;
    int next = curr * 10 + node.val;
    if (node.left == null && node.right == null) {
        total += next;
        return;
    }
    dfs(node.left, next);
    dfs(node.right, next);
}

💻 The Code

// Recursive DFS; Java stays classy
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int sum) {
        if (node == null) return 0;
        sum = sum * 10 + node.val;
        if (node.left == null && node.right == null) return sum;
        return dfs(node.left, sum) + dfs(node.right, sum);
    }
}
 // Iterative DFS, if recursion gives you nightmares
import java.util.*;
class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        int total = 0;
        Stack<pair integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, root.val));
        while (!stack.isEmpty()) {
            Pair<treenode integer> p = stack.pop();
            TreeNode n = p.getKey();
            int v = p.getValue();
            if (n.left == null && n.right == null) total += v;
            if (n.right != null) stack.push(new Pair<>(n.right, v * 10 + n.right.val));
            if (n.left != null) stack.push(new Pair<>(n.left, v * 10 + n.left.val));
        }
        return total;
    }
}
</treenode></pair>

⚠️ Pitfalls, Traps & Runtime Smacks

• Leaf means no left and no right—not “has at least one child.”
• If you only sum digits, you’ll get a number smaller than the sample output, and the interviewer will make ‘that’ face.
• Accumulator not isolated by path? Expect wild results.
• Time: O(n); Space: O(h)—unless your BD use case is a stick, then congrats on your recursion depth.

🧠 Interviewer Brain-Tattoo

Remember: building numbers in a tree is like moving decimal places—skip that, and your code’s logic is as hollow as a node with no children. Use place value, spare yourself the “easy” label on LeetCode shame.