Sum Root to Leaf Numbers

Medium

Sum Root to Leaf Numbers

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the tree can hold? Can they be negative?
Can the tree be empty or contain only a single node?
What should I return if the root is null (empty tree)? Should I return 0?
Are the node values guaranteed to be single digits (0-9), or can they be larger?
By 'root-to-leaf' path, do you mean a path starting from the root and ending at a leaf node (a node with no children)?

Brute Force Solution

Approach

The brute force strategy involves exploring every single path from the top of the tree to the bottom. For each path, we'll construct a number and then add up all the numbers to get our final answer. It's like trying every route in a maze to find all the possible end points.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Go down every possible path from the top to a leaf (the bottom of the tree).
As you go down each path, build a number by adding the value of each node you visit to the end of your number.
Once you reach a leaf, you have a complete number for that path.
Add that number to a running total.
Repeat this process for every single path from the top to a leaf.
When you've explored every path and added all the numbers, the running total is your final answer.

Code Implementation

def sum_root_to_leaf(root):
    total_sum = 0

    def calculate_path_sum(node, current_number):
        nonlocal total_sum

        if not node:
            return

        # Build the number as we traverse down the tree
        current_number = current_number * 10 + node.val

        if not node.left and not node.right:
            # Reached a leaf node, add current number to the total
            total_sum += current_number

            return

        calculate_path_sum(node.left, current_number)

        calculate_path_sum(node.right, current_number)

    calculate_path_sum(root, 0)
    return total_sum

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses all nodes in the binary tree. In the worst-case scenario, the tree might be skewed, resembling a linked list, where visiting each node is necessary. Since we visit each of the n nodes in the tree once to compute the sum of root-to-leaf numbers, the time complexity is directly proportional to the number of nodes. Therefore, the algorithm has a time complexity of O(n).

Space Complexity

O(H) – The described brute-force approach uses recursion to explore each path from the root to a leaf. The space complexity is determined by the maximum depth of the recursion, which corresponds to the height (H) of the binary tree. In the worst-case scenario (a skewed tree), H can be equal to N (the number of nodes). Thus, the maximum space used by the call stack is proportional to the height of the tree, resulting in a space complexity of O(H).

Optimal Solution

Approach

We want to find the total value of numbers formed by paths from the root of a tree down to each leaf. The clever approach involves building up each number step-by-step as we travel down the tree and adding that number to a running total when we hit a leaf.

Here's how the algorithm would work step-by-step:

Start at the root of the tree with an initial number of zero.
As you move from a parent node to a child node, update the current number by multiplying it by ten and then adding the child's value.
If you reach a leaf node (a node with no children), add the current number to a running total.
Repeat this process for all paths from the root to the leaves.
The final running total will be the sum of all root-to-leaf numbers.

Code Implementation

def sum_numbers(root):
    total_sum = 0

    def calculate_sum(node, current_number):
        nonlocal total_sum

        if not node:
            return

        # Build number as we traverse.
        current_number = current_number * 10 + node.val

        # Leaf node condition
        if not node.left and not node.right:
            total_sum += current_number

            return

        # Explore left subree.
        calculate_sum(node.left, current_number)

        # Explore right subtree.
        calculate_sum(node.right, current_number)

    calculate_sum(root, 0)

    # Return accumulated sum
    return total_sum

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the binary tree, visiting each node exactly once. The amount of work done at each node (multiplying the current number by 10 and adding the node's value) is constant. Therefore, the time complexity is directly proportional to the number of nodes in the tree, which is denoted as n. The algorithm avoids redundant calculations because it builds the numbers step by step while going down the tree, so the complexity is O(n).

Space Complexity

O(H) – The algorithm employs recursion to traverse the tree. The maximum depth of the recursion stack is determined by the height (H) of the tree, as each recursive call corresponds to moving one level deeper. In the worst-case scenario (a skewed tree), H can be equal to N (the number of nodes), but in a balanced tree, H would be log N. Therefore, the auxiliary space complexity due to the recursion stack is O(H), where H is the height of the tree.

Edge Cases

Case	How to Handle
Null root node	Return 0 if the root is null, as there's no path and thus no sum.
Single node tree (root only)	Return the value of the root node itself since it's both the root and the leaf.
Tree with very large depth, potentially causing stack overflow with recursion	Consider iterative DFS or BFS to avoid stack overflow errors from excessive recursion depth.
Tree with very large numbers, potentially leading to integer overflow when concatenating the path number	Use a larger data type (e.g., long) to store the number, or use modular arithmetic to prevent overflow.
Tree with all nodes having the value 0	The algorithm should correctly sum the paths formed by all zeros (e.g., a path of 0 -> 0 should result in the number 0).
Unbalanced tree with highly skewed distribution of node values	The algorithm should handle unbalanced trees efficiently; the performance will be affected by the tree's height, but the correctness will be preserved.
Tree containing leading zeros in a path (e.g., 0 -> 1)	The standard approach of building the number concatenating from root to leaf will correctly form the number (e.g., path 0->1 will create the number 1 and not require any special handling).
Nodes with negative values (invalid in the problem context but good to clarify)	Clarify with the interviewer whether negative values are allowed, and if so, how to handle them, as the problem description implies non-negative single digit values for each node.