Deepest Leaves Sum - Video Solutions

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.