1302. Deepest Leaves Sum
Problem Description
The problem presents us with a binary tree, where each node contains an integer value. Our task is to find the sum of the values that reside in the deepest leaves of the tree. To clarify, the deepest leaves are the nodes at the bottom most level of the tree, which have no children.
Intuition
The intuition behind the solution is to traverse the entire tree to find the deepest leaves and accumulate their values. We can approach this problem using either Depth-First Search (DFS) or Breadth-First Search (BFS).
DFS would involve a recursive function that keeps track of the current level and compares it against the maximum level found so far. If the node being visited is a leaf and is at the deepest level seen so far, its value is added to the running sum.
However, the provided solution utilizes BFS, which is a suitable approach for this type of problem because BFS explores the tree level by level. We use a queue to keep track of nodes to visit and proceed through each level of the tree one by one. As we traverse and exhaust all nodes on a particular level, we can be confident that eventually, we will reach the deepest level. By summing all values at that final level, we get the sum of all the deepest leaves.
We can implement BFS in Python using a queue (in this case, a deque for efficiency reasons). We initiate the queue with the root node, and in each iteration, we process all nodes at the current level (queue size determines the level width). For each node, we add its value to a sum accumulator and extend the queue with its children, if any. When the loop ends, the sum accumulator contains the sum of the values at the deepest level, which is the final answer we want to return.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
Which data structure is used to implement recursion?
Solution Approach
The solution uses the Breadth-First Search (BFS) pattern to solve the problem. BFS is ideal for this problem since it processes nodes level by level. In this approach, the algorithm makes use of a deque, which is a double-ended queue that allows for efficient addition and removal of elements from both ends.
Here's a step-by-step breakdown of the algorithm incorporated in the solution:
- Initialize a
dequewith the root of the binary tree. - Initiate a loop that runs as long as there are nodes present in the
deque. - Reset the sum accumulator
ansto 0 at the start of each level. - Determine the number of nodes present at the current level by checking the length of the
deque. - For each node of the current level, pop it from the left side of the
deque. - Add the value of the current node to the accumulator
ans. - Check if the current node has a left child, if so, append it to the right side of the
deque. - Check if the current node has a right child, if so, append it to the right side of the
deque. - At the end of the level, all node values will have been added to
ans, we then proceed to the next level (if any). - Once the loop exits, it means we have visited all levels. The last accumulated sum stored in
ansis the sum of all the values of the deepest leaves in the binary tree.
In terms of algorithmic efficiency, at each level n, all n nodes are processed, and each node is added to the queue once. This results in an O(N) time complexity, where N is the number of nodes in the binary tree. The space complexity is O(N) in the worst case, when the tree is complete, and the bottom level is full (half of the nodes are on the last level).
What's the relationship between a tree and a graph?
Example Walkthrough
Let's take an example binary tree to walk through the BFS solution approach.
1 1 2 / \ 3 2 3 4 / \ \ 5 4 5 6 6 / / \ 7 7 8 9
Now we apply the BFS algorithm step-by-step:
-
We initialize a
dequewith the root of the binary tree. In this case, the root is the node with value1. -
There's a node in the
deque(the root), so we begin the loop. -
Reset the sum accumulator
ansto 0. This holds the sum of values at the current level. -
Determine the number of nodes present at the current level. Initially, this is 1 since we start with just the root.
-
We pop the node with value
1from the left side of the deque and add its value toans.ansnow becomes1. -
We check for the left and right children of node
1. Both exist, so we append them to the right side of the deque. The deque now holds nodes2and3. -
Moving to the second level, we reset
ansto 0. The deque has 2 nodes, so we will process both nodes2and3. -
For both nodes, we remove them from the deque, add their values to
ans, and add their children to the deque. After processing,ansis2 + 3 = 5, and the deque now holds nodes4,5, and6. -
Continuing to the third level, we reset
ansto 0 again. The deque has 3 nodes, so it represents the third level. -
We process nodes
4,5, and6as before. We add their values toans, and add their children to the deque. After this level,ansis4 + 5 + 6 = 15and the deque holds7,8, and9. -
At the fourth level, we process the final nodes
7,8, and9, add their values toans, which is now7 + 8 + 9 = 24, and since there are no more children, the deque becomes empty. -
As the deque is now empty, the loop exits. At this point,
ansholds the sum of all the deepest leaf nodes, which is24. This sum is the final answer, and it is the sum of the values of the deepest leaves in our example binary tree:7,8, and9.
By following these steps, applying BFS allowed us to efficiently find the sum of the deepest leaves in the binary tree for our example. The algorithm progresses level by level, and the running sum at the last level gives us our answer.
Solution Implementation
1from collections import deque # Import deque for queue operations
2
3# Definition for a binary tree node.
4class TreeNode:
5 def __init__(self, val=0, left=None, right=None):
6 self.val = val
7 self.left = left
8 self.right = right
9
10class Solution:
11 def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
12 # Initialize a queue with the root node
13 queue = deque([root])
14
15 while queue: # Continue until the queue is empty
16 level_sum = 0 # Sum of values at the current level
17 level_count = len(queue) # Number of nodes at the current level
18
19 # Iterate over all nodes at the current level
20 for _ in range(level_count):
21 node = queue.popleft() # Remove the node from the queue
22 level_sum += node.val # Add the node's value to the level sum
23
24 # If the node has a left child, add it to the queue
25 if node.left:
26 queue.append(node.left)
27
28 # If the node has a right child, add it to the queue
29 if node.right:
30 queue.append(node.right)
31
32 # After the loop, level_sum contains the sum of values of the deepest leaves
33 return level_sum
341/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8 TreeNode() {}
9 TreeNode(int val) { this.val = val; }
10 TreeNode(int val, TreeNode left, TreeNode right) {
11 this.val = val;
12 this.left = left;
13 this.right = right;
14 }
15}
16
17/**
18 * Solution class to find the sum of the deepest leaves in a binary tree.
19 */
20class Solution {
21 /**
22 * Computes the sum of the deepest leaves in the binary tree.
23 *
24 * @param root the root node of the binary tree.
25 * @return the sum of the deepest leaves.
26 */
27 public int deepestLeavesSum(TreeNode root) {
28 // Initialize a queue to perform level-order traversal
29 Deque<TreeNode> queue = new ArrayDeque<>();
30 queue.offer(root);
31
32 // Variable to store the sum of the values of the deepest leaves
33 int sum = 0;
34
35 // Perform level-order traversal of the tree
36 while (!queue.isEmpty()) {
37 sum = 0; // Reset sum for the current level
38 // Process all nodes at the current level
39 for (int size = queue.size(); size > 0; --size) {
40 TreeNode currentNode = queue.pollFirst();
41 // Add the value of the current node to the sum
42 sum += currentNode.val;
43 // If the left child exists, add it to the queue for the next level
44 if (currentNode.left != null) {
45 queue.offer(currentNode.left);
46 }
47 // If the right child exists, add it to the queue for the next level
48 if (currentNode.right != null) {
49 queue.offer(currentNode.right);
50 }
51 }
52 // The loop goes back to process the next level, if any
53 }
54 // After the loop, sum contains the sum of the deepest leaves
55 return sum;
56 }
57}
581#include <queue>
2
3// Definition for a binary tree node.
4struct TreeNode {
5 int val; // Value of the node
6 TreeNode *left; // Pointer to the left child
7 TreeNode *right; // Pointer to the right child
8
9 // Constructor to initialize the node with no children
10 TreeNode() : val(0), left(nullptr), right(nullptr) {}
11
12 // Constructor to initialize the node with a given value and no children
13 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14
15 // Constructor to initialize the node with a value and left and right children
16 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17};
18
19class Solution {
20public:
21 // Function that computes the sum of values of the deepest leaves in a binary tree
22 int deepestLeavesSum(TreeNode* root) {
23 int sumAtCurrentDepth = 0; // This will hold the sum of the nodes at the current depth
24 // Queue to hold the nodes at the current level for breadth-first traversal
25 std::queue<TreeNode*> nodeQueue;
26 nodeQueue.push(root);
27
28 // Perform level order traversal (breadth-first traversal) of the tree
29 while (!nodeQueue.empty()) {
30 sumAtCurrentDepth = 0; // Reset the sum at the start of each level
31 // Process all nodes at the current level
32 for (int i = nodeQueue.size(); i > 0; --i) {
33 TreeNode* currentNode = nodeQueue.front(); // Get the front node in the queue
34 nodeQueue.pop(); // Remove the node from the queue
35
36 // Add the node's value to the sum of the current depth/level
37 sumAtCurrentDepth += currentNode->val;
38
39 // If there is a left child, add it to the queue for the next level
40 if (currentNode->left) nodeQueue.push(currentNode->left);
41 // If there is a right child, add it to the queue for the next level
42 if (currentNode->right) nodeQueue.push(currentNode->right);
43 }
44 }
45 // Return the sum of the deepest leaves (sum of the last level processed)
46 return sumAtCurrentDepth;
47 }
48};
491// Definition for a binary tree node.
2class TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6
7 constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 this.val = (val === undefined ? 0 : val);
9 this.left = (left === undefined ? null : left);
10 this.right = (right === undefined ? null : right);
11 }
12}
13
14/**
15 * Calculate the sum of the deepest leaves in a binary tree.
16 * @param {TreeNode | null} root - The root of the binary tree.
17 * @return {number} The sum of the deepest leaves' values.
18 */
19function deepestLeavesSum(root: TreeNode | null): number {
20 // If the root is null, return 0 as there are no nodes.
21 if (root === null) {
22 return 0;
23 }
24
25 // Initialize a queue to perform a level-order traversal of the tree.
26 const queue: TreeNode[] = [root];
27 let currentLevelSum = 0; // This will hold the sum of the values of the current level nodes.
28
29 // Perform a level-order traversal to find the deepest leaves.
30 while (queue.length !== 0) {
31 const numberOfNodesAtCurrentLevel = queue.length;
32 let sum = 0; // Initialize sum for the current level.
33
34 // Process all nodes at the current level.
35 for (let i = 0; i < numberOfNodesAtCurrentLevel; i++) {
36 // Get the next node from the queue.
37 const node = queue.shift();
38 if (node) {
39 // Accumulate the values of nodes at this level.
40 sum += node.val;
41
42 // If the node has a left child, add it to the queue for the next level.
43 if (node.left) {
44 queue.push(node.left);
45 }
46
47 // If the node has a right child, add it to the queue for the next level.
48 if (node.right) {
49 queue.push(node.right);
50 }
51 }
52 }
53
54 // After processing all nodes at the current level, the sum becomes
55 // the result as it represents the sum of the deepest leaves seen so far.
56 currentLevelSum = sum;
57 }
58
59 // Return the sum of the values of the deepest leaves.
60 return currentLevelSum;
61}
62Which algorithm should you use to find a node that is close to the root of the tree?
Time and Space Complexity
Time Complexity
The time complexity of the code is O(N), where N is the total number of nodes in the binary tree. This is because the algorithm uses a breadth-first search (BFS) approach to traverse each node in the tree exactly once to calculate the sum of the deepest leaves.
Space Complexity
The space complexity of the code is O(N), where N is the maximum width of the tree or the maximum number of nodes at any level of the tree. In the worst-case scenario (e.g., a complete binary tree), this is essentially the number of nodes at the last level. The space complexity comes from the queue used to store nodes at each level while performing BFS.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.