Deepest Leaves Sum solution and explanation
Google
9 more videos on this problem
LeetCode 1302. Deepest Leaves Sum (Algorithm Explained)Nick White · 7:25 · 13K views
Deepest Leaves Sum | Live Coding with Explanation | Leetcode - 1302Algorithms Made Easy · 6:19 · 4K views
Leetcode Medium 1302. Deepest Leaves SumCode with Alisha · 10:01 · 3K views
Leetcode - Deepest Leaves Sum (Python)Timothy H Chang · 3:45 · 1K views
1302. Deepest Leaves Sum - LeetCode Python SolutionCode with Carter · 6:25 · 627 views
Leetcode 1302: Deepest Leaves SumAlgorithms Casts · 12:25 · 614 views
LeetCode - 1302. Deepest Leaves Sum | Day 11 April ChallengeAditya Mahajan · 11:38 · 601 views
Deepest Leaves Sum | Leetcode 1302Coding Decoded · 7:00 · 559 views
Deepest Leaves Sum - LeetCode 1302 - JavaScriptAlgoJS · 5:49 · 457 views
Leetcode 1302. Deepest Leaves Sum | DFS Solution Explained | Code in pythonPlacement Corner · 8:50 · 321 views
The problem
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, 104]. 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.
from collections import deque
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: TreeNode) -> int:
q = deque([root])
while q:
sum_level = 0
for _ in range(len(q)):
node = q.popleft()
sum_level += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return sum_levelimport java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int deepestLeavesSum(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int sum = 0;
while (!queue.isEmpty()) {
int size = queue.size();
sum = 0;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return sum;
}
}#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int deepestLeavesSum(TreeNode* root) {
if (!root) return 0;
std::queue<TreeNode*> q;
q.push(root);
int sum = 0;
while (!q.empty()) {
int size = q.size();
sum = 0;
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
sum += node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return sum;
}class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
var deepestLeavesSum = function(root) {
if (!root) return 0;
let queue = [root];
let sum = 0;
while (queue.length > 0) {
sum = 0;
let size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
sum += node.val;
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
}
return sum;
};#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int deepestLeavesSum(TreeNode* root) {
if (!root) return 0;
TreeNode** queue = malloc(10000 * sizeof(TreeNode*));
int head = 0, tail = 0;
queue[tail++] = root;
int sum = 0;
while (head < tail) {
int level_size = tail - head;
sum = 0;
for (int i = 0; i < level_size; i++) {
TreeNode* node = queue[head++];
sum += node->val;
if (node->left) queue[tail++] = node->left;
if (node->right) queue[tail++] = node->right;
}
}
free(queue);
return sum;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int DeepestLeavesSum(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
int sum = 0;
while (queue.Count > 0) {
int size = queue.Count;
sum = 0;
for (int i = 0; i < size; i++) {
TreeNode node = queue.Dequeue();
sum += node.val;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
}
return sum;
}
}The Python solution uses a deque for efficient pop operations. It updates the sum per level and finally returns the last level's sum, which corresponds to the deepest leaves.
Time Complexity: O(n)
Space Complexity: O(n)
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.max_depth = 0
self.sum = 0
def dfs(self, node, depth):
if not node:
return
if depth > self.max_depth:
self.max_depth = depth
self.sum = node.val
elif depth == self.max_depth:
self.sum += node.val
self.dfs(node.left, depth + 1)
self.dfs(node.right, depth + 1)
def deepestLeavesSum(self, root: TreeNode) -> int:
self.dfs(root, 0)
return self.sumclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
int maxDepth = 0;
int sum = 0;
public void dfs(TreeNode node, int depth) {
if (node == null) return;
if (depth > maxDepth) {
maxDepth = depth;
sum = node.val;
} else if (depth == maxDepth) {
sum += node.val;
}
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
public int deepestLeavesSum(TreeNode root) {
dfs(root, 0);
return sum;
}
}#include <iostream>
#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxDepth = 0;
int sum = 0;
void dfs(TreeNode* node, int depth) {
if (!node) return;
if (depth > maxDepth) {
maxDepth = depth;
sum = node->val;
} else if (depth == maxDepth) {
sum += node->val;
}
dfs(node->left, depth + 1);
dfs(node->right, depth + 1);
}
int deepestLeavesSum(TreeNode* root) {
dfs(root, 0);
return sum;
}
};class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
var deepestLeavesSum = function(root) {
let maxDepth = 0;
let sum = 0;
const dfs = (node, depth) => {
if (!node) return;
if (depth > maxDepth) {
maxDepth = depth;
sum = node.val;
} else if (depth === maxDepth) {
sum += node.val;
}
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
};
dfs(root, 0);
return sum;
};#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void dfs(TreeNode* node, int depth, int* maxDepth, int* sum) {
if (!node) return;
if (depth > *maxDepth) {
*maxDepth = depth;
*sum = node->val;
} else if (depth == *maxDepth) {
*sum += node->val;
}
dfs(node->left, depth + 1, maxDepth, sum);
dfs(node->right, depth + 1, maxDepth, sum);
}
int deepestLeavesSum(TreeNode* root) {
int maxDepth = -1, sum = 0;
dfs(root, 0, &maxDepth, &sum);
return sum;
}using System;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int maxDepth = 0;
private int sum = 0;
private void DFS(TreeNode node, int depth) {
if (node == null) return;
if (depth > maxDepth) {
maxDepth = depth;
sum = node.val;
} else if (depth == maxDepth) {
sum += node.val;
}
DFS(node.left, depth + 1);
DFS(node.right, depth + 1);
}
public int DeepestLeavesSum(TreeNode root) {
DFS(root, 0);
return sum;
}
}Python solution employs DFS with a class-based approach to track maximum depth and sum similarly, adjusting values as depth varies.
Time Complexity: O(n)
Space Complexity: O(h)
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function deepestLeavesSum(root: TreeNode | null): number {
let q: TreeNode[] = [root];
let ans = 0;
while (q.length) {
const nq: TreeNode[] = [];
ans = 0;
for (const { val, left, right } of q) {
ans += val;
left && nq.push(left);
right && nq.push(right);
}
q = nq;
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deepestLeavesSum(root *TreeNode) (ans int) {
q := []*TreeNode{root}
for len(q) > 0 {
ans = 0
for k := len(q); k > 0; k-- {
node := q[0]
q = q[1:]
ans += node.Val
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
pub fn deepest_leaves_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut q = VecDeque::new();
q.push_back(root);
let mut ans = 0;
while !q.is_empty() {
ans = 0;
for _ in 0..q.len() {
if let Some(Some(node)) = q.pop_front() {
let node = node.borrow();
ans += node.val;
if node.left.is_some() {
q.push_back(node.left.clone());
}
if node.right.is_some() {
q.push_back(node.right.clone());
}
}
}
}
ans
}
}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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function deepestLeavesSum(root: TreeNode | null): number {
let [ans, mx] = [0, 0];
const dfs = (root: TreeNode | null, i: number) => {
if (!root) {
return;
}
if (i > mx) {
mx = i;
ans = root.val;
} else if (i === mx) {
ans += root.val;
}
dfs(root.left, i + 1);
dfs(root.right, i + 1);
};
dfs(root, 1);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deepestLeavesSum(root *TreeNode) int {
ans, mx := 0, 0
var dfs func(*TreeNode, int)
dfs = func(root *TreeNode, i int) {
if root == nil {
return
}
if i == mx {
ans += root.Val
} else if i > mx {
mx = i
ans = root.Val
}
dfs(root.Left, i+1)
dfs(root.Right, i+1)
}
dfs(root, 1)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Level Order Traversal (BFS) | Time Complexity: O(n) |
| Depth-First Search (DFS) | Time Complexity: O(n) |
| BFS | – |
| DFS | – |
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. |
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.