Sum Root to Leaf Numbers - Practice Coding Problems

Sum Root to Leaf Numbers - Problem

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number. For example, the root-to-leaf path 1 → 2 → 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Input & Output

Example 1 — Simple Binary Tree

$ Input: root = [1,2,3]

› Output: 25

💡 Note: Root-to-leaf paths: 1→2 gives number 12, and 1→3 gives number 13. Sum: 12 + 13 = 25

Example 2 — Deeper Tree

$ Input: root = [4,9,0,5,1]

› Output: 1026

💡 Note: Root-to-leaf paths: 4→9→5 gives 495, 4→9→1 gives 491, 4→0 gives 40. Sum: 495 + 491 + 40 = 1026

Example 3 — Single Node

$ Input: root = [5]

› Output: 5

💡 Note: Only one node, so the single root-to-leaf path is just 5

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with digits 0-9 as node values

Find Paths

Each root-to-leaf path forms a number (1→2 = 12, 1→3 = 13)

Sum Numbers

Add all root-to-leaf numbers together (12 + 13 = 25)

Key Takeaway

🎯 Key Insight: Build numbers incrementally during DFS traversal instead of storing all paths

Asked in

a Amazon 45 G Google 38 M Microsoft 32 🍎 Apple 28

The key insight is to use DFS traversal while building numbers incrementally rather than storing all paths. As we traverse from root to leaf, we multiply the current number by 10 and add the current digit. Best approach is DFS with number building. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Store All Paths	O(n)	O(n)	Find all root-to-leaf paths, convert each to number, then sum
DFS - Build Numbers During Traversal	O(n)	O(h)	Use DFS to traverse tree while building numbers incrementally

Brute Force - Store All Paths — Algorithm Steps

Find all root-to-leaf paths using DFS
Convert each path array to integer
Sum all numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Paths

Traverse tree to find all root-to-leaf paths: [1,2], [1,3]

Convert

Convert each path to number: [1,2] → 12, [1,3] → 13

Sum

Add all numbers: 12 + 13 = 25

Code -

solution.c — C

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void findPaths(struct TreeNode* node, int* currentPath, int pathLen, int allPaths[][1000], int* pathLens, int* pathCount) {
    if (!node) return;
    
    currentPath[pathLen] = node->val;
    pathLen++;
    
    if (!node->left && !node->right) {
        for (int i = 0; i < pathLen; i++) {
            allPaths[*pathCount][i] = currentPath[i];
        }
        pathLens[*pathCount] = pathLen;
        (*pathCount)++;
    } else {
        findPaths(node->left, currentPath, pathLen, allPaths, pathLens, pathCount);
        findPaths(node->right, currentPath, pathLen, allPaths, pathLens, pathCount);
    }
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    int allPaths[1000][1000];
    int pathLens[1000];
    int pathCount = 0;
    int currentPath[1000];
    
    findPaths(root, currentPath, 0, allPaths, pathLens, &pathCount);
    
    int totalSum = 0;
    for (int i = 0; i < pathCount; i++) {
        int number = 0;
        for (int j = 0; j < pathLens[i]; j++) {
            number = number * 10 + allPaths[i][j];
        }
        totalSum += number;
    }
    
    return totalSum;
}

int main() {
    // For simplicity, create a small test case
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once to find paths, then process each path

✓ Linear Growth

Space Complexity

O(n)

Store all paths and recursion stack depth

⚡ Linearithmic Space

182.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Store All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler