Jobs

Interviews

Discussions

Deepest Leaves Sum

Medium

Google

1 view

Topics:

TreesRecursion

You are given the root of a binary tree. Your task is to return the sum of values of its deepest leaves. A deepest leaf is a node with no children that is farthest from the root. For example, a tree with only the root node has a single deepest leaf, the root itself.

Consider the following examples:

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Explanation: The deepest leaves are the nodes with values 7 and 8. Therefore, the sum is 7 + 8 = 15.

Example 2:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19
Explanation: The deepest leaves are the nodes with values 9, 1, 4, and 5. Therefore, the sum is 9 + 1 + 4 + 5 = 19.

Given these examples, write an algorithm to efficiently calculate the sum of the values of the deepest leaves in a given binary tree. What is the time and space complexity of your solution?

Deepest Leaves Sum

Medium

Google

1 view

Topics:

TreesRecursion

Consider the following examples:

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Explanation: The deepest leaves are the nodes with values 7 and 8. Therefore, the sum is 7 + 8 = 15.

Example 2:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19
Explanation: The deepest leaves are the nodes with values 9, 1, 4, and 5. Therefore, the sum is 9 + 1 + 4 + 5 = 19.

Given these examples, write an algorithm to efficiently calculate the sum of the values of the deepest leaves in a given binary tree. What is the time and space complexity of your solution?

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 for each node in the binary tree? Can node values be negative, zero, or only positive?
What constitutes an empty tree? Should I return 0, null, or throw an exception if the root is null?
Are there any constraints on the height or the number of nodes in the tree?
If there are multiple nodes at the deepest level, am I expected to return their sum as an integer, or is there a possibility of overflow requiring a different data type (like long)?
Could you provide an example of a binary tree and the expected output to ensure I fully understand the problem statement?

Brute Force Solution

Approach

The core idea is to explore every single path from the top of the tree down to the leaves. We will find the depth of each leaf and keep track of the deepest level we encounter. Then we'll sum up the values of all the leaves at that deepest level.

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

Go through every possible path from the top of the tree down to each leaf (the very bottom node).
For each leaf, figure out how far down it is from the top (its depth).
Keep track of the biggest depth we've seen so far. This is the depth of the deepest leaves.
Once we've found the depth of all the leaves, go back and look at only the leaves that are at the deepest level.
Add up the values of all the leaves that are at the deepest level. This is the sum we are looking for.

Code Implementation

def deepest_leaves_sum(root):
    deepest_level = 0
    leaves_sums = 0

    def dfs(node, level):
        nonlocal deepest_level, leaves_sums

        # If we hit a null node, simply return.
        if not node:
            return

        # If we hit a leaf node, check if we need to update deepest_level and leaves_sums.
        if not node.left and not node.right:
            if level > deepest_level:
                # We have a new deepest level
                deepest_level = level
                leaves_sums = node.val

            elif level == deepest_level:
                # Accumulate nodes at the deepest level
                leaves_sums += node.val
            return

        dfs(node.left, level + 1)

        dfs(node.right, level + 1)

    dfs(root, 0)

    return leaves_sums

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree once during the depth-first traversal to determine the depth of each leaf and to update the maximum depth encountered. After finding the maximum depth, the algorithm performs another traversal to sum the values of the nodes at the deepest level. Since each node is visited at most twice (once to find its depth and possibly again to sum its value if it's at the deepest level), where n is the number of nodes in the tree, the time complexity is O(n).

Space Complexity

O(H) – The space complexity is determined by the recursion depth of the tree traversal, where H is the height of the tree. In the worst case (skewed tree), the recursion stack can grow to the height of the tree, requiring O(H) space for the function call stack. The algorithm does not use any other significant auxiliary data structures besides the recursion stack. Therefore, the space complexity is O(H), which can be O(N) in the worst-case scenario (skewed tree) where N is the number of nodes.

Optimal Solution

Approach

The most efficient way to find the sum of the deepest leaves is to explore the tree level by level. We keep track of the current deepest level and its corresponding sum, updating it whenever we encounter a new deepest level.

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

Start exploring the tree from the very top.
As you move down the tree, keep track of the current level you're on.
If you find a level that's deeper than any level you've seen before, discard any previous sums and start a new sum for this deeper level.
If you find a level that's as deep as the deepest level you've seen, add the values of the leaves at this level to the running sum for that level.
Keep going until you've explored every part of the tree.
The final sum you have for the deepest level is the answer.

Code Implementation

def deepestLeavesSum(root):
    deepest_level_sum = 0
    max_depth = -1

    def dfs(node, current_depth):
        nonlocal deepest_level_sum, max_depth

        if not node:
            return

        #If deeper level found, reset sum
        if current_depth > max_depth:
            deepest_level_sum = node.val
            max_depth = current_depth

        elif current_depth == max_depth:
            #If same level, add to the sum
            deepest_level_sum += node.val

        dfs(node.left, current_depth + 1)
        dfs(node.right, current_depth + 1)

    dfs(root, 0)
    return deepest_level_sum

Big(O) Analysis

Time Complexity

O(n) – The provided solution employs a level-order traversal (Breadth-First Search) to explore the tree. In a level-order traversal, each node in the tree is visited exactly once. Therefore, the time complexity is directly proportional to the number of nodes in the tree, where n represents the total number of nodes. Consequently, the algorithm's runtime scales linearly with the input size, resulting in a time complexity of O(n).

Space Complexity

O(W) – The algorithm explores the tree level by level, effectively using a queue (implicitly or explicitly) to store the nodes at each level for processing. In the worst-case scenario (e.g., a complete binary tree or a skewed tree), the widest level of the tree could contain up to W nodes, where W represents the maximum width of the tree. Therefore, the auxiliary space used is proportional to the maximum width of the tree, leading to a space complexity of O(W).

Edge Cases

Case	How to Handle
Null root node	Return 0 immediately as there are no nodes to sum.
Single node tree	Return the value of the root node since it's the only deepest node.
Tree with all positive values	Standard traversal will correctly calculate the sum.
Tree with all negative values	Standard traversal will correctly calculate the negative sum.
Tree with a mix of positive, negative and zero values	Standard traversal will correctly handle the sum.
Deeply skewed tree (e.g., linked list structure)	The depth-first or breadth-first traversal should handle potentially large depth without stack overflow issues for a balanced input, although highly unbalanced inputs may impact recursion depth.
Maximum integer value for node values to detect integer overflow	Use long data type for storing sum to prevent potential integer overflow when summing the values at deepest level.
Perfectly balanced tree with large number of nodes	BFS approach might consume a lot of memory in the queue; DFS is typically more memory-efficient for balanced trees.

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 for each node in the binary tree? Can node values be negative, zero, or only positive?
What constitutes an empty tree? Should I return 0, null, or throw an exception if the root is null?
Are there any constraints on the height or the number of nodes in the tree?
If there are multiple nodes at the deepest level, am I expected to return their sum as an integer, or is there a possibility of overflow requiring a different data type (like long)?
Could you provide an example of a binary tree and the expected output to ensure I fully understand the problem statement?

Brute Force Solution

Approach

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

Go through every possible path from the top of the tree down to each leaf (the very bottom node).
For each leaf, figure out how far down it is from the top (its depth).
Keep track of the biggest depth we've seen so far. This is the depth of the deepest leaves.
Once we've found the depth of all the leaves, go back and look at only the leaves that are at the deepest level.
Add up the values of all the leaves that are at the deepest level. This is the sum we are looking for.

Code Implementation

def deepest_leaves_sum(root):
    deepest_level = 0
    leaves_sums = 0

    def dfs(node, level):
        nonlocal deepest_level, leaves_sums

        # If we hit a null node, simply return.
        if not node:
            return

        # If we hit a leaf node, check if we need to update deepest_level and leaves_sums.
        if not node.left and not node.right:
            if level > deepest_level:
                # We have a new deepest level
                deepest_level = level
                leaves_sums = node.val

            elif level == deepest_level:
                # Accumulate nodes at the deepest level
                leaves_sums += node.val
            return

        dfs(node.left, level + 1)

        dfs(node.right, level + 1)

    dfs(root, 0)

    return leaves_sums

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start exploring the tree from the very top.
As you move down the tree, keep track of the current level you're on.
If you find a level that's deeper than any level you've seen before, discard any previous sums and start a new sum for this deeper level.
If you find a level that's as deep as the deepest level you've seen, add the values of the leaves at this level to the running sum for that level.
Keep going until you've explored every part of the tree.
The final sum you have for the deepest level is the answer.

Code Implementation

def deepestLeavesSum(root):
    deepest_level_sum = 0
    max_depth = -1

    def dfs(node, current_depth):
        nonlocal deepest_level_sum, max_depth

        if not node:
            return

        #If deeper level found, reset sum
        if current_depth > max_depth:
            deepest_level_sum = node.val
            max_depth = current_depth

        elif current_depth == max_depth:
            #If same level, add to the sum
            deepest_level_sum += node.val

        dfs(node.left, current_depth + 1)
        dfs(node.right, current_depth + 1)

    dfs(root, 0)
    return deepest_level_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return 0 immediately as there are no nodes to sum.
Single node tree	Return the value of the root node since it's the only deepest node.
Tree with all positive values	Standard traversal will correctly calculate the sum.
Tree with all negative values	Standard traversal will correctly calculate the negative sum.
Tree with a mix of positive, negative and zero values	Standard traversal will correctly handle the sum.
Deeply skewed tree (e.g., linked list structure)	The depth-first or breadth-first traversal should handle potentially large depth without stack overflow issues for a balanced input, although highly unbalanced inputs may impact recursion depth.
Maximum integer value for node values to detect integer overflow	Use long data type for storing sum to prevent potential integer overflow when summing the values at deepest level.
Perfectly balanced tree with large number of nodes	BFS approach might consume a lot of memory in the queue; DFS is typically more memory-efficient for balanced trees.