#1302

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Deepest Leaves Sum

Find the sum of the deepest leaves in a binary tree by using tree traversal and state tracking techniques.

tree depth first search breadth first search binary tree

Problem Statement

You are given the root of a binary tree. You need to find the sum of the values of the nodes at the deepest level. The deepest leaves of a binary tree are the nodes that are furthest from the root, and the sum of their values is what you need to compute.

A tree is represented as a binary structure, with each node containing a value and links to left and right children. Your task is to calculate the sum of the deepest leaves efficiently. The input will consist of the root of the tree, and the expected output is a single integer representing this sum.

Examples

Example 1

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]

Output: 15

Example details omitted.

Example 2

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Output: 19

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 100

Solution Approach

Breadth-First Search (BFS)

BFS is a natural choice for finding nodes at the deepest level, as it explores the tree level by level. By traversing the tree from top to bottom, we can determine the deepest level and sum the leaf values of that level.

Depth-First Search (DFS)

DFS is another option for this problem. By recursively exploring all the paths in the tree, we can track the maximum depth and sum the leaf values of nodes at that depth. DFS provides a more explicit approach to tracking the depth.

Tracking Maximum Depth During Traversal

Whether using BFS or DFS, you can track the current maximum depth of the tree during traversal. Once the deepest level is identified, summing the values of the leaves at that level will yield the desired result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of nodes in the tree, as both BFS and DFS will visit each node once. The space complexity depends on the traversal method: BFS uses O(w) space, where w is the maximum width of the tree, while DFS uses O(h) space, where h is the tree's height due to recursion stack.

What Interviewers Usually Probe

Tests the candidate's understanding of tree traversal techniques.
Evaluates problem-solving strategies related to tree depth and leaf-level summing.
Looks for the candidate's ability to choose between BFS and DFS based on problem needs.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem’s requirement to only sum the deepest leaves.
Confusing the depth of the tree with the level of leaves.
Incorrectly handling the case when there is only one node in the tree.

Follow-up variants

Change the tree structure to allow non-binary trees and ask for the sum of deepest leaves.
Ask for the sum of the deepest odd or even numbered leaves.
Add extra constraints like calculating the sum at multiple levels, not just the deepest.

FAQ

What is the main pattern to solve the Deepest Leaves Sum problem?

The problem is solved using binary-tree traversal and state tracking, specifically with either BFS or DFS to track depth and sum the deepest leaves.

How does Breadth-First Search help in solving this problem?

BFS helps by traversing the tree level by level, allowing us to easily identify the deepest level and sum the values of the leaves at that level.

What if the tree is unbalanced, how does it affect the solution?

The solution will still work for unbalanced trees as both BFS and DFS methods account for varying depths and leaf distributions.

Can we solve the problem using recursion?

Yes, DFS with recursion can track the current depth of the tree and sum the values of leaves at the deepest level.

What is the time complexity of solving the Deepest Leaves Sum problem?

The time complexity is O(n), where n is the number of nodes in the tree, since every node must be visited during traversal.

terminal

Solution

Solution 1: BFS

We can use breadth-first search (BFS) to traverse the binary tree level by level, and calculate the sum of the node values at each level. After completing the traversal, return the sum of the node values at the last level.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            ans = 0
            for _ in range(len(q)):
                node = q.popleft()
                ans += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

Solution 2: DFS

We can use depth-first search (DFS) to recursively traverse the binary tree while keeping track of the current node's depth, the maximum depth, and the sum of the deepest leaf nodes. When visiting the current node, if the current node's depth equals the maximum depth, add the current node's value to the sum of the deepest leaf nodes. If the current node's depth is greater than the maximum depth, update the maximum depth to the current node's depth and update the sum of the deepest leaf nodes to the current node's value.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            ans = 0
            for _ in range(len(q)):
                node = q.popleft()
                ans += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

Continue Practicing

#1315 sum of nodes with even valued grandparent #1261 find elements in a contaminated binary tree #1361 validate binary tree nodes