Is Deepest Leaves Sum easy or hard?

Deepest Leaves Sum is classified as a Medium problem on LeetCode. The traversal logic itself is straightforward, but recognizing that the deepest level can be captured using BFS or tracked with DFS depth requires familiarity with binary tree traversal patterns.

Deepest Leaves Sum Python/Java solution

In Python or Java, the BFS implementation uses a queue (collections.deque in Python or LinkedList in Java) to process nodes by level. The DFS version uses recursion with variables tracking the maximum depth and running sum. Both implementations achieve O(n) time complexity.

How to solve Deepest Leaves Sum in O(n)?

Traverse the binary tree once while tracking depth information. In BFS, compute the sum for each level and return the last level's sum. In DFS, track the current depth and update the deepest-level sum whenever a deeper node is found. Both strategies ensure each node is processed exactly once.

What is the best approach for Deepest Leaves Sum?

Level Order Traversal (BFS) is typically the best approach because it processes the tree one level at a time. The last level encountered during BFS is the deepest level, so the algorithm simply keeps track of the sum of nodes at each level. This solution runs in O(n) time and O(n) space.

Is Deepest Leaves Sum asked at Google/Amazon/Meta?

Tree traversal problems similar to Deepest Leaves Sum frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often involve computing values at specific depths, level-order traversal, or aggregating results across tree levels.

What data structure is used in Deepest Leaves Sum?

The problem uses a binary tree as the primary data structure. The BFS approach relies on a queue to process nodes level by level, while the DFS approach uses recursion (call stack) to track traversal depth.

What is the time complexity of Deepest Leaves Sum?

Both BFS and DFS solutions run in O(n) time because every node in the binary tree is visited exactly once. Space complexity is O(n) for BFS due to the queue and O(h) to O(n) for DFS depending on the recursion depth.

Description Hints 2 Solution Video 7:25

1302. Deepest Leaves Sum

Medium86.3% acceptance3 companies

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

Example 1:

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

Example 2:

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

Constraints:

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

Asked at 3 companies

Myntra Tiktok

Google

Topics

Hints open one at a time

Hint 1

Traverse the tree to find the max depth.

Hint 2

Traverse the tree again to compute the sum required.

7:25

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3,4,5,null,6,7,null,null,null,null,8]

Input

[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Your code is saved on this device.Solution