We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Deepest Leaves Sum

Difficulty: Medium

Problem Description

Given the root of a binary tree, return the sum of values of its deepest leaves.

Key Insights

  • The deepest leaves are the nodes located at the maximum depth of the binary tree.
  • A level-order traversal (BFS) can be used to traverse the tree level by level, allowing us to keep track of the sum of values at each level.
  • A depth-first search (DFS) can also be used to determine the maximum depth and then sum the values of the leaves at that depth.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we need to visit each node. Space Complexity: O(H), where H is the height of the tree, for the recursion stack in DFS or the queue in BFS.

Solution

To solve the problem, we can use a breadth-first search (BFS) approach to traverse the tree level by level. Each time we move to the next level, we will reset our sum and accumulate the values of the nodes at the current level. By the time we reach the deepest level, our sum will contain the sum of the deepest leaves.

  1. Use a queue to facilitate level-order traversal.
  2. For each level, reset the sum and iterate through all nodes at that level, adding their values to the sum.
  3. Continue this process until you have processed all levels of the tree.
  4. The final value of the sum will be the answer.

Code Solutions

from collections import deque

def deepestLeavesSum(root):
    if not root:
        return 0

    queue = deque([root])
    deepest_sum = 0

    while queue:
        deepest_sum = 0
        level_size = len(queue)

        for _ in range(level_size):
            node = queue.popleft()
            deepest_sum += node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return deepest_sum
← Back to All Questions