Sum Root to Leaf Numbers

Medium
1912.

Sum Root to Leaf Numbers

Sum Root to Leaf Numbers is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

You are given the root of a binary tree in which every node holds a single digit from 0 to 9. Each root-to-leaf path spells a number: the digits read from the root down to the leaf (a node with no children). For example the path 1 → 2 → 3 spells 123.

Return the sum of the numbers spelled by all root-to-leaf paths. The answer fits in a 32-bit signed integer.

Example 1

Input
root = [1,2,3]
Output
25
Explanation
The paths spell 12 and 13, and 12 + 13 = 25.

Example 2

Input
root = [4,9,0,5,1]
Output
1026
Explanation
The paths spell 495, 491 and 40, and 495 + 491 + 40 = 1026.

Example 3

Input
root = [0,1]
Output
1
Explanation
The only path spells 01, which is the number 1.

Constraints

  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 9
  • the depth of the tree does not exceed 10
  • the answer fits in a 32-bit signed integer
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum Root to Leaf Numbers — Solution in Python, Java & C++

Sum Root to Leaf Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sum Root to Leaf Numbers is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the root of a binary tree in which every node holds a single digit from 0 to 9. Each root-to-leaf path spells a number: the digits read from the root down to the leaf (a node with no children). For example the path 1 → 2 → 3 spells 123.

Return the sum of the numbers spelled by all root-to-leaf paths. The answer fits in a 32-bit signed integer.

Example 1

Input: root = [1,2,3]
Output: 25
Explanation: The paths spell 12 and 13, and 12 + 13 = 25.

Example 2

Input: root = [4,9,0,5,1]
Output: 1026
Explanation: The paths spell 495, 491 and 40, and 495 + 491 + 40 = 1026.

Example 3

Input: root = [0,1]
Output: 1
Explanation: The only path spells 01, which is the number 1.

Constraints

  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 9
  • the depth of the tree does not exceed 10
  • the answer fits in a 32-bit signed integer

Hints for Sum Root to Leaf Numbers

  1. Hint 1

    Appending a digit d to a number x gives 10 * x + d.

  2. Hint 2

    Walk from the root downwards carrying the number spelled so far.

  3. Hint 3

    At a leaf the carried number is complete — add it to the total. An inner node only passes its number on to its children.

How to solve Sum Root to Leaf Numbers

Carry the number spelled so far down a depth-first walk; at each node it becomes 10 * carried + digit, and each leaf contributes the number that reaches it.

Approach

  1. Visit the root with a carried value of 0.
  2. At a node, set cur = 10 * carried + node.val.
  3. If the node is a leaf, return cur.
  4. Otherwise return the sum of the results for its existing children, each visited with cur.

Why it works

The value reaching a node is exactly the number spelled by the path from the root to it, by induction: the root gets its own digit, and a child gets its parent's number with its digit appended. Every leaf is reached once, so every root-to-leaf number is added once.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • A node with one child is not a leaf — do not count its partial number.
  • Leading zeros are fine: the path 0 → 1 spells 1.

Reference solution

Python

from typing import Optional

def sumNumbers(root: Optional[TreeNode]) -> int:
    def walk(node, cur):
        cur = cur * 10 + node.val
        if node.left is None and node.right is None:
            return cur
        total = 0
        if node.left:
            total += walk(node.left, cur)
        if node.right:
            total += walk(node.right, cur)
        return total

    return walk(root, 0) if root else 0

Java

public static int sumNumbers(TreeNode root) {
    return root == null ? 0 : digitWalk(root, 0);
}

static int digitWalk(TreeNode node, int cur) {
    cur = cur * 10 + node.val;
    if (node.left == null && node.right == null) return cur;
    int total = 0;
    if (node.left != null) total += digitWalk(node.left, cur);
    if (node.right != null) total += digitWalk(node.right, cur);
    return total;
}

C++

int digitWalk(TreeNode* node, int cur);

int sumNumbers(TreeNode* root) {
    return root ? digitWalk(root, 0) : 0;
}

int digitWalk(TreeNode* node, int cur) {
    cur = cur * 10 + node->val;
    if (!node->left && !node->right) return cur;
    int total = 0;
    if (node->left) total += digitWalk(node->left, cur);
    if (node->right) total += digitWalk(node->right, cur);
    return total;
}

JavaScript

var sumNumbers = function(root) {
    return root === null ? 0 : digitWalk(root, 0);
};

var digitWalk = function(node, cur) {
    cur = cur * 10 + node.val;
    if (node.left === null && node.right === null) return cur;
    var total = 0;
    if (node.left !== null) total += digitWalk(node.left, cur);
    if (node.right !== null) total += digitWalk(node.right, cur);
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals