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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Deepest Leaves Sum

Number: 1254

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

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

Key Insights

  • The problem requires finding all the leaves at the deepest level of the tree.
  • Breadth-first search (BFS) naturally processes the tree level by level.
  • Depth-first search (DFS) can also be used by tracking the depth and summing values when the maximum depth is encountered.
  • BFS can update the sum for each level, and the sum from the last processed level is the result.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes since each node is visited once. Space Complexity: O(n) due to the queue in BFS (or recursion stack in DFS in the worst-case scenario).

Solution

We can solve this problem using a Breadth-First Search (BFS) approach. We maintain a queue that holds all nodes at the current level. For each level, we:

  • Initialize a sum variable.
  • Process all nodes at that level by dequeuing each node and adding its value to the sum.
  • Add the node's children (if any) to the queue for processing the next level. After processing all levels, the sum from the final level is the sum of the deepest leaves.

Alternatively, a Depth-First Search (DFS) approach could be used by traversing the tree and keeping track of the maximum depth and updating the result when that depth increases.

Code Solutions

# Python solution using Breadth-First Search (BFS)
from collections import deque

def deepestLeavesSum(root):
    # Initialize the queue with the root node
    queue = deque([root])
    # Variable to store the sum of the deepest leaves
    deepest_sum = 0
    
    # Process each level of the tree
    while queue:
        # Initialize the level sum for the current level
        level_sum = 0
        # Number of nodes at the current level
        level_length = len(queue)
        
        # Process all nodes at the current level
        for _ in range(level_length):
            node = queue.popleft()
            level_sum += node.val  # Add node's value to current level sum
            
            # If the left child exists, add it to the queue
            if node.left:
                queue.append(node.left)
            # If the right child exists, add it to the queue
            if node.right:
                queue.append(node.right)
        
        # After processing the level, update deepest_sum with level_sum
        deepest_sum = level_sum
        
    # Return the sum of the deepest leaves
    return deepest_sum
← Back to All Questions