Deepest Leaves Sum - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumTree Depth-First Search Breadth-First Search Binary Tree23 min readAsked at: Google, Myntra, Tiktok

Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given the root of a binary tree, compute the sum of all node values located at the deepest level. The task is to identify the maximum depth of the tree and add the values of every node that appears at that level.

Approach 1: Level Order Traversal (BFS) (Time: O(n), Space: O(n))

This approach performs a breadth-first traversal using a queue. Process the tree level by level. For each level, iterate through all nodes currently in the queue and compute their sum while pushing their children into the queue for the next level. The key observation: the final level processed in BFS is the deepest level. Keep overwriting the level sum during traversal, and once the queue becomes empty, the last computed sum represents the sum of the deepest leaves. This method works naturally with level-based problems and is often the most intuitive solution when the task explicitly depends on tree depth. BFS uses a queue and may hold up to O(n) nodes in the worst case (for a wide tree). Learn more about Breadth-First Search and how it applies to Binary Tree problems.

Approach 2: Depth-First Search (DFS) with Depth Tracking (Time: O(n), Space: O(h) to O(n))

DFS explores the tree recursively while tracking the current depth. Maintain two variables: maxDepth and sum. When visiting a node, compare its depth with maxDepth. If the depth exceeds maxDepth, update maxDepth and reset the sum to the node's value. If the depth equals maxDepth, add the node value to the sum. Continue exploring both left and right subtrees. By the time traversal completes, the sum contains values of all nodes at the deepest level. The recursion stack uses O(h) space for balanced trees and up to O(n) in the worst-case skewed tree. This method is flexible when you need depth information during traversal and integrates naturally with recursive Depth-First Search patterns.

Recommended for interviews: Level Order Traversal (BFS) is usually the expected solution because the problem directly refers to the deepest level, which BFS exposes naturally by processing nodes layer by layer. DFS with depth tracking demonstrates stronger understanding of recursive tree traversal and state management. Showing both approaches during discussion signals solid grasp of tree traversal strategies.

Approach 1: Level Order Traversal (BFS)

This approach leverages a Breadth-First Search (BFS) traversal method using a queue to explore each level of the binary tree fully before moving on to the next level. By summing values at each level during the traversal, we can determine the sum of the deepest leaves by replacing the sum at every level.

We initialize a queue and push the root node into it. Then, we iterate while the queue is not empty, processing all nodes at the current level and updating the sum. If there are nodes left to explore after processing a level, we reset the sum for the next level.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n), for storing nodes in the queue.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS)

This alternative approach uses Depth-First Search (DFS) to traverse the binary tree and keeps track of the maximum depth and accumulated sum of the node values at that depth.

In this C implementation, we perform a DFS, updating the max depth and sum at that depth. When equal to max depth, accumulate the node values.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(h), where h is the height of the tree due to recursion stack.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the tree.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Approach 4: 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.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the tree.

Code

Python Java C++Go TypeScript C

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Level Order Traversal (BFS)	Time Complexity: O(n), where n is the number of nodes in the binary tree. Space Complexity: O(n), for storing nodes in the queue.
Depth-First Search (DFS)	Time Complexity: O(n) Space Complexity: O(h), where h is the height of the tree due to recursion stack.
BFS	—
DFS	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Level Order Traversal (BFS)	O(n)	O(n)	Best when solving level-based tree problems where you need values from a specific depth.
Depth-First Search (DFS) with Depth Tracking	O(n)	O(h) to O(n)	Useful when recursion is preferred or when depth information must be tracked during traversal.

Video Solution

LeetCode 1302. Deepest Leaves Sum (Algorithm Explained) • Nick White • 13,169 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Deepest Leaves Sum with our built-in code editor and test cases.

Practice on FleetCode

Binary Tree Inorder Traversal

Unique Binary Search Trees II

Problem Info

DifficultyMedium

Acceptance86.3%

Approaches4

Reading time23 min

Asked at

Google Myntra Tiktok

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Level Order Traversal (BFS)

Code

Complexity

Approach 2: Depth-First Search (DFS)

Code

Complexity

Approach 3: BFS

Code

Approach 4: DFS

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents