129. Sum Root to Leaf Numbers

Problem Description

In this problem, we have a binary tree where each node contains a digit from 0 to 9. We need to find the total sum of all the numbers represented by all possible root-to-leaf paths in the tree. A root-to-leaf path is a sequence of nodes from the root of the tree down to a leaf node such that we concatenate the values of all the nodes along the path to form a number. For example, if a path has nodes with values 1, 2, and 3 in that order, the number formed is 123. Finally, we sum all these numbers to get the final result. It is also given that the final sum will be within the range of a 32-bit integer.

To solve the problem, we traverse the tree and explore all possible paths from the root to the leaves. A binary tree does not necessarily have a balanced number of nodes, so some paths may be longer than others, and we need to make sure we include all paths in our calculation. Each path effectively represents a number in base 10, where the depth of the node determines the place value of its digit.

Intuition

The solution is based on Depth-First Search (DFS) traversal because we want to explore each path from the root to the leaves without missing any. The DFS approach allows us to accumulate the value of the number as we traverse the tree by shifting the current accumulated value one place value to the left (multiplying by 10) and then adding the value of the current node.

For implementing DFS, we perform the following steps:

Start at the root node (initial state).
As we move down to a child node, we update the current number by shifting the current number one place value to the left (by multiplying by 10) and adding the value of the current node to it.
If we reach a leaf node (a node without children), we add the current number to the sum since this represents a complete number from root to leaf.
We continue the process by exploring all paths; if a node has both left and right children, we explore each branch in separate recursive calls.
Finally, the sum of all the root-to-leaf numbers is returned.

This recursive implementation keeps the logic straightforward and uses the call stack to backtrace once we hit a leaf, naturally allowing us to move on to other paths in the tree.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a good use case for backtracking?

Combinatorial problemsRandom number generationTopological sortingMatrix multiplication

I don’t know

Solution Approach

The solution uses a Depth-First Search (DFS) approach to traverse the binary tree and calculate the sum of all root-to-leaf numbers. DFS is a standard tree traversal algorithm that can be implemented recursively to traverse all the paths in a tree down to its leaves, which fits perfectly with the problem's requirement of exploring each possible root-to-leaf path.

Here's a step-by-step breakdown of the DFS algorithm as implemented in the solution:

Begin DFS with the root node of the binary tree and an initial current sum s set to 0. The current sum s holds the numeric value represented by the path from the root to the current node.
At each node, update s to represent the current path's number. This is done by shifting the current accumulated value one decimal place to the left (which is equivalent to multiplying it by 10) and then adding the node's value. For a node with value v, this operation is s = s * 10 + v.
If the current node is a leaf (both its left and right child are None), the current path represents a complete number, so return this current sum s.
To explore all paths, recursively apply the DFS to the left and right children of the current node (if they exist). Use the updated s for these recursive calls.
At each node, if the node is not a leaf, the return value is the sum of the results from the left and right recursive calls. This is because the current path's numeric value s should be added to the final result only once, at the leaf nodes.
The base case for the recursion is when the current node is None (a nullptr), which means we've gone past a leaf node. In this case, return 0 because there's no number to add to the sum.
The recursion ends when all paths have been traversed. The final return value of dfs(root, 0) will be the total sum of all root-to-leaf numbers.

Here is the core code for the DFS function from the solution:

1def dfs(root, s):
2    if root is None:
3        return 0
4    s = s * 10 + root.val
5    if root.left is None and root.right is None:
6        return s
7    return dfs(root.left, s) + dfs(root.right, s)

This recursive function (dfs) clearly illustrates the DFS approach. It's invoked initially with dfs(root, 0), which triggers the DFS traversal from the root of the tree with an initial sum of 0.

In summary, the DFS pattern, executed through recursive calls, provides a clear and structured way to visit every node in the tree while maintaining the state (s) necessary to accumulate the numerical value of the current path. As the problem requires examining all possible paths, DFS ensures that each leaf is reached, and every path's value is computed and added to produce the total sum.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's consider a small binary tree as an example:

For this tree, there are three possible root-to-leaf paths:

1 -> 2 -> 4, which forms the number 124
1 -> 2 -> 5, which forms the number 125
1 -> 3, which forms the number 13

Now, let's go through the solution using the Depth-First Search (DFS) approach to calculate the sum of all the numbers that are formed by root-to-leaf paths.

We start with the root node with a value of 1 and an initial sum s of 0.

At the root node (1), we update s to s * 10 + 1, which is 1.
We move to the left child (2). Now s is 1 * 10 + 2 = 12.
1. At node (2) we have two children, so we apply DFS to the left child (4). Now s becomes 12 * 10 + 4 = 124. Since (4) is a leaf node, we return 124.
2. We also need to consider the right child (5). We apply DFS to (5) with s as 12 * 10 + 5 = 125. Since (5) is also a leaf node, we return 125.
The sum at node (2) will be the sum from its left and right children which is 124 + 125 = 249.

Now we go back to the root (1) and explore the right child (3).

At node (3), s is updated to 1 * 10 + 3 = 13. Since (3) is a leaf node, we return 13.
Finally, we add the sums from both children of the root node, which are 249 (from the left subtree) and 13 (from the right subtree) to get the final sum which is 249 + 13 = 262.

Thus, the sum of all root-to-leaf numbers in the tree is 262.

Solution Implementation

1class TreeNode:
2    # TreeNode class definition is provided for context.
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val  # The value of the node.
5        self.left = left  # Pointer to the left child.
6        self.right = right  # Pointer to the right child.
7
8class Solution:
9    def sumNumbers(self, root: TreeNode) -> int:
10        # Helper function to perform depth-first search.
11        def dfs(node, num_sum):
12            # If the current node is None, we've reached a leaf or the tree is empty.
13            if not node:
14                return 0
15          
16            # Update the sum for the current path: 
17            # previous sum times 10 plus the current node's value.
18            num_sum = num_sum * 10 + node.val
19          
20            # If we're at a leaf node, return the current sum.
21            if not node.left and not node.right:
22                return num_sum
23          
24            # Continue the depth-first search on left and right subtrees, adding their sums.
25            return dfs(node.left, num_sum) + dfs(node.right, num_sum)
26      
27        # Start the depth-first search with the root node and an initial sum of 0.
28        return dfs(root, 0)
29

1// Definition for a binary tree node.
2class TreeNode {
3    int val; // Value of the node
4    TreeNode left; // Left child
5    TreeNode right; // Right child
6  
7    // Constructors
8    TreeNode() {}
9    TreeNode(int val) { this.val = val; }
10    TreeNode(int val, TreeNode left, TreeNode right) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17class Solution {
18    // This method starts the process of summing up all the numbers formed by the root-to-leaf paths.
19    public int sumNumbers(TreeNode root) {
20        return depthFirstSearch(root, 0);
21    }
22
23    // Helper method to perform depth-first search on the tree.
24    // It accumulates the values from the root to each leaf, forming the numbers.
25    private int depthFirstSearch(TreeNode node, int sum) {
26        // If the current node is null, return 0 as there are no numbers to form here.
27        if (node == null) {
28            return 0;
29        }
30
31        // Update the current sum by appending the current node value.
32        sum = sum * 10 + node.val;
33
34        // If we reached a leaf, return the sum as we completed the formation of one number.
35        if (node.left == null && node.right == null) {
36            return sum;
37        }
38
39        // Continue the DFS traversal by visiting the left and right subtrees and summing the numbers formed.
40        return depthFirstSearch(node.left, sum) + depthFirstSearch(node.right, sum);
41    }
42}
43

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    // Constructor initializes current node and its children to default (no children and value 0).
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    // Constructor initializes current node with a value and sets children to default (no children).
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    // Constructor initializes current node with a value and left and right children.
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    int sumNumbers(TreeNode* root) {
17        // Recursive function to traverse the tree and calculate the sum.
18        // It carries two parameters: the current node and the sum calculated so far.
19        std::function<int(TreeNode*, int)> depthFirstSearch = [&](TreeNode* node, int currentSum) -> int {
20            // Base case: if the current node is null, return 0 as there's nothing to add.
21            if (!node) return 0;
22            // Update current sum by appending the current node's value.
23            currentSum = currentSum * 10 + node->val;
24            // If at a leaf node, return the current sum.
25            if (!node->left && !node->right) return currentSum;
26            // Recursively call the function for left and right children, and return their sum.
27            return depthFirstSearch(node->left, currentSum) + depthFirstSearch(node->right, currentSum);
28        };
29        // Start the depth first search with the root node and initial sum of 0.
30        return depthFirstSearch(root, 0);
31    }
32};
33

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6  
7    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14/**
15 * Computes the total sum of all numbers represented by the paths from the root to the leaf nodes.
16 * @param {TreeNode | null} root - The root node of the binary tree.
17 * @return {number} The total sum of the numbers.
18 */
19function sumNumbers(root: TreeNode | null): number {
20    /**
21     * A helper function to perform a depth-first search on the binary tree.
22     * @param {TreeNode | null} node - The current node in the traversal.
23     * @param {number} currentSum - The number formed by the path from the root to the current node.
24     * @return {number} The sum of all numbers formed by paths from the root to leaf nodes.
25     */
26    function depthFirstSearch(node: TreeNode | null, currentSum: number): number {
27        // Base case: if the current node is null, return 0 as there's no number to add.
28        if (node === null) {
29            return 0;
30        }
31
32        // Update the current sum by adding the current node's value to it.
33        // This effectively shifts the previous sum by one decimal place to the left and adds the current node's value.
34        currentSum = currentSum * 10 + node.val;
35
36        // Check if the current node is a leaf node (i.e., no left or right children).
37        if (node.left === null && node.right === null) {
38            // If it's a leaf node, return the current sum which represents a complete number from the root to this leaf.
39            return currentSum;
40        }
41      
42        // Recursively call the function for the left and right children and return the sum of both calls.
43        // This effectively adds up the sums of all paths from root to the leaves.
44        return depthFirstSearch(node.left, currentSum) + depthFirstSearch(node.right, currentSum);
45    }
46  
47    // Initialize the depth-first search with the root node and an initial sum of 0.
48    return depthFirstSearch(root, 0);
49}
50

Not Sure What to Study? Take the 2-min Quiz：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(N), where N is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once by the depth-first search (DFS) algorithm.

Space Complexity

The space complexity of the code is O(H), where H is the height of the tree. This accounts for the maximum number of function calls on the call stack at any given time during the execution of the DFS, which is essentially the depth of the recursion. In the worst case, when the tree is skewed, the height of the tree would be N, making the space complexity O(N). However, in a balanced tree, the space complexity would be O(log N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

129. Sum Root to Leaf Numbers

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings