Leetcode 129. Sum Root to Leaf Numbers

129. Sum Root to Leaf Numbers

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.

Approach 1:


class Solution {
    public int sumNumbers(TreeNode root) {
        int root2leaf = 0;
        int currentNumber = 0;
        Deque> stack = new ArrayDeque();
        stack.push(new Pair(root, 0));

        while (!stack.isEmpty()) {
            Pair p = stack.pop();
            root = p.getKey();
            currentNumber = p.getValue();

            if (root != null) {
                currentNumber = currentNumber * 10 + root.val;

                if (root.left == null && root.right == null) { // if leaf node found
                    root2leaf += currentNumber;
                } else { // if leaf node not found
                    stack.push(new Pair(root.right, currentNumber));
                    stack.push(new Pair(root.left, currentNumber));
                }
            }
        }
        return root2leaf;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Introduction

The "Sum Root to Leaf Numbers" problem is a common tree-based problem where you are given a binary tree, and you need to find the sum of all numbers formed by root-to-leaf paths. A leaf node is defined as a node that has no children, and the number formed by a path is created by concatenating the values of the nodes along the path from the root to the leaf.

Problem Statement

Given the root of a binary tree, each node contains a single digit, and each root-to-leaf path represents a number formed by concatenating the node values along the path. Return the total sum of all root-to-leaf numbers.

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

The tree node structure is given above. The goal is to calculate the sum of all the numbers formed by the root-to-leaf paths.

Approach

To solve this problem, we can use depth-first search (DFS) to traverse the tree. As we traverse each node, we maintain a running total of the number formed so far by the path from the root to the current node. When we reach a leaf node, the running total is a complete number, and we add it to the final sum.

Start by performing a DFS traversal from the root node.
At each node, update the number formed by the path so far. This is done by multiplying the current number by 10 and adding the node's value.
If a leaf node is reached (a node with no left or right child), add the current number to the total sum.
Recursively repeat this process for the left and right children of the current node.

Algorithm

The algorithm follows these steps:

Define a helper function that performs a DFS traversal while maintaining the current number formed along the path.
At each node, calculate the number formed by multiplying the current number by 10 and adding the node’s value.
If the current node is a leaf, add the formed number to the total sum.
Recursively traverse the left and right subtrees of each node.
Return the total sum once the DFS traversal is complete.

This approach ensures that every root-to-leaf path is considered and its corresponding number is added to the total sum.

Example

Consider the following binary tree:

In this example, the following root-to-leaf paths and their corresponding numbers can be found: - Path 1: 1 → 2 → 4 (number = 124) - Path 2: 1 → 2 → 5 (number = 125) - Path 3: 1 → 3 (number = 13)

The sum of these numbers is: 124 + 125 + 13 = 262.

Code Implementation

Below is the Python implementation of the algorithm to find the sum of root-to-leaf numbers:

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

def sumNumbers(root):
    def dfs(node, current_sum):
        if not node:
            return 0
        
        # Update the current number formed so far
        current_sum = current_sum * 10 + node.val
        
        # If it's a leaf node, return the current number
        if not node.left and not node.right:
            return current_sum
        
        # Recursively sum the numbers in the left and right subtrees
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)
    
    return dfs(root, 0)

In this code: - The `dfs` function is a recursive helper that calculates the sum of all numbers formed by the root-to-leaf paths. - At each node, it updates the current sum by multiplying the existing sum by 10 and adding the node’s value. - If the node is a leaf node (i.e., it has no left or right child), it returns the current sum. - Otherwise, it recursively sums the numbers from the left and right subtrees. - The main function `sumNumbers` calls the `dfs` function starting from the root node with an initial sum of 0.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited once during the DFS traversal.

The space complexity is O(h), where h is the height of the tree. This space is used by the recursion stack during the DFS traversal. In the worst case, the height of the tree is O(n) (for a skewed tree), and in the best case, it is O(log n) (for a balanced tree).

Conclusion

The "Sum Root to Leaf Numbers" problem is an excellent example of how depth-first search (DFS) can be used to traverse a binary tree and calculate a sum based on path values. By maintaining the current number formed by the path and adding it when we reach a leaf node, we can easily compute the sum of all root-to-leaf numbers in the tree.