Sum Root to Leaf Numbers

This question turns a tree into numbers. Each path from the top to a bottom node spells out a number, one digit at a time. You add up all those numbers. The interviewer wants to see if you can build a value as you walk down a path. That building-as-you-go skill is useful far beyond this one problem.

🎯 The Problem

You get the root of a binary tree. A binary tree is a structure where each node has at most two children. Add up the numbers spelled by every root-to-leaf path.

The rules:

• Every node holds a single digit from zero to nine.
• Each path from the root down to a leaf forms a number. A leaf is a node with no children.
• Read the digits from the root to that leaf, top to bottom, to make the number.
• Add up the numbers from all the root-to-leaf paths and return the total.

Input:  root = [1, 2, 3]
Output: 25

      1
     / \
    2   3

Explanation: Path 1->2 makes 12. Path 1->3 makes 13. Sum is 12 + 13 = 25.

There are two paths here. The path 1 then 2 spells the number 12. The path 1 then 3 spells 13. We add 12 + 13 and get 25.

Here is the tree. Each leaf finishes one path and one number.

🐢 Approach 1: Collect Paths Then Convert (Brute Force)

Find every full path first, then turn each path into a number, then add them.

The idea:

• Walk the tree and collect each root-to-leaf path as a list of digits.
• One path might be [1, 2] and another [1, 3].

How it works:

• After you have all the paths, read each list’s digits in order to build its number.
• Sum every number.

Why it is weak:

• It stores full lists of digits, which costs extra memory.
• It does a second pass to rebuild numbers from those lists.
• That is two separate efforts for one answer.

Here is the collect-paths code:

def sum_numbers(root):
    paths = []
    def dfs(node, path):
        if not node: return
        path += str(node.val)
        if not node.left and not node.right: paths.append(path)
        dfs(node.left, path); dfs(node.right, path)
    dfs(root, "")
    return sum(int(path) for path in paths)

⚡ Approach 2: DFS Building the Number Inline (Best)

The idea in one line: build the number while you walk down, not after, by carrying a running number with you.

The idea:

• The running number is the value spelled by the digits from the root to where you are now.
• To add a new digit, do current = current * 10 + digit.
• Multiplying by ten makes room. Then the new digit drops into the ones spot.

How it works:

• Start at root 1, so the number is 1.
• Move to child 2: 1 * 10 + 2 is 12. That matches the path 1 then 2.
• At a leaf, the running number is the full number for that path. Add it to the total.

Why it is best:

• One walk, no extra path lists.
• It uses only the call stack for memory.

This diagram shows the running number growing as we go down each path.

Steps to Solve

1. Start a DFS from the root with the running number set to zero.
2. At each node, update the running number to current * 10 + node value.
3. If the node is a leaf, return the running number, because the path is complete.
4. If the node has children, walk into the left child and the right child with the updated number.
5. Add the totals from both sides.
6. Return the grand total from the root.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int sumNumbers(Node* node, int current) {
    if (node == NULL) return 0;
    current = current * 10 + node->val;       // add this digit
    if (node->left == NULL && node->right == NULL) {
        return current;                       // leaf: path is done
    }
    return sumNumbers(node->left, current)
         + sumNumbers(node->right, current);
}

int main(void) {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);

    printf("%d\n", sumNumbers(root, 0));
    return 0;
}

25

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int sumNumbers(Node* node, int current) {
    if (!node) return 0;
    current = current * 10 + node->val;       // add this digit
    if (!node->left && !node->right) {
        return current;                       // leaf: path is done
    }
    return sumNumbers(node->left, current)
         + sumNumbers(node->right, current);
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);

    cout << sumNumbers(root, 0) << endl;
    return 0;
}

25

public class SumRootToLeaf {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    public static int sumNumbers(Node node, int current) {
        if (node == null) return 0;
        current = current * 10 + node.val;        // add this digit
        if (node.left == null && node.right == null) {
            return current;                       // leaf: path is done
        }
        return sumNumbers(node.left, current)
             + sumNumbers(node.right, current);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);

        System.out.println(sumNumbers(root, 0));
    }
}

25

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def sum_numbers(node, current):
    if node is None:
        return 0
    current = current * 10 + node.val        # add this digit
    if node.left is None and node.right is None:
        return current                       # leaf: path is done
    return (sum_numbers(node.left, current)
            + sum_numbers(node.right, current))


root = Node(1)
root.left = Node(2)
root.right = Node(3)

print(sum_numbers(root, 0))

25

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function sumNumbers(node, current) {
  if (node === null) return 0;
  current = current * 10 + node.val;         // add this digit
  if (node.left === null && node.right === null) {
    return current;                          // leaf: path is done
  }
  return sumNumbers(node.left, current) + sumNumbers(node.right, current);
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);

console.log(sumNumbers(root, 0));

25

Let us walk through the Python version line by line.

The function starts with if node is None: return 0. An empty spot adds nothing to the sum. So we return zero and that branch ends.

The key line is current = current * 10 + node.val. The current is the number spelled by the path above this node. Multiplying by ten shifts every digit up one place and leaves a zero in the ones spot. Then adding node.val drops this node’s digit into that spot. So if current was 1 and the node is 2, we get 12.

The check if node.left is None and node.right is None tests for a leaf. A leaf has no children, so the path stops here. The running number is now the full number for this path. So we return current. That value flows back up to be added into the total.

If the node is not a leaf, the last line walks both children. We pass the updated current to each. Each call returns the sum of all numbers under that side. We add the left result and the right result together and return that.

Each return adds its part to the caller’s sum. So the root’s call ends up with the sum of every root-to-leaf number, which we print. We start the whole thing with current equal to zero, so the first multiply leaves only the root’s digit.

⏱️ Time and Space Complexity

The brute force and the DFS both visit every node once, so both are O(n) in time where n is the number of nodes. The difference is the extra work. The brute force stores full paths and then rebuilds numbers from them, which costs more memory and a second pass. The DFS builds each number as it walks, so it needs no path lists. For space, both use the call stack, which goes as deep as the tree. So the space is O(h), where h is the height. The neat part is building the number inline, with the simple times ten plus digit step.

🧩 Key Takeaways

• ✅ Each root-to-leaf path spells one number, read top to bottom.
• ✅ Build the number as you walk with current * 10 + node value.
• ✅ A leaf has no children, so that is where a path and its number end.
• ✅ Add up the numbers from every leaf to get the answer.
• ✅ Building inline avoids storing full paths, so it uses less memory.

🚀 What’s Next?

• Count Good Nodes in Binary Tree
• Maximum Depth of Binary Tree