1302. Deepest Leaves Sum

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

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.

Flowchart Walkthrough

Let's use the algorithm flowchart to analyze LeetCode problem 1302: Deepest Leaves Sum. You can refer to the flowchart here: Flowchart. Here's the step-by-step breakdown:

Is it a graph?

Yes: The problem involves a binary tree, which can be considered a type of graph where each node has edges connecting to its child nodes.

Is it a tree?

Yes: The data structure described is specifically a binary tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: Although a tree is a DAG, the problem does not pertain to the properties specific to DAGs like topological sorting.

Is the problem related to shortest paths?

No: The objective is to sum the values of the deepest leaves, not to find the shortest path.

Conclusion: The flowchart recommends using Depth-First Search (DFS) for this tree-based problem to traverse through each node and track the level, calculating the sum of nodes at the deepest level.

By using DFS, we can efficiently record the maximum depth encountered during the traversal and accumulate the sums of nodes at this depth, leading to the solution for the problem.

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.

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 deque with 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 ans to 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 ans is 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).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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 deque with the root of the binary tree. In this case, the root is the node with value 1.
There's a node in the deque (the root), so we begin the loop.
Reset the sum accumulator ans to 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 1 from the left side of the deque and add its value to ans. ans now becomes 1.
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 nodes 2 and 3.
Moving to the second level, we reset ans to 0. The deque has 2 nodes, so we will process both nodes 2 and 3.
For both nodes, we remove them from the deque, add their values to ans, and add their children to the deque. After processing, ans is 2 + 3 = 5, and the deque now holds nodes 4, 5, and 6.
Continuing to the third level, we reset ans to 0 again. The deque has 3 nodes, so it represents the third level.
We process nodes 4, 5, and 6 as before. We add their values to ans, and add their children to the deque. After this level, ans is 4 + 5 + 6 = 15 and the deque holds 7, 8, and 9.
At the fourth level, we process the final nodes 7, 8, and 9, add their values to ans, which is now 7 + 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, ans holds the sum of all the deepest leaf nodes, which is 24. 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, and 9.

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
34

1/**
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}
58

1#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};
49

1// 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}
62

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: