2583. Kth Largest Sum in a Binary Tree
Problem Description
This LeetCode problem requires finding the kth largest level sum in a binary tree. A level sum is defined as the total value of all nodes at the same depth, where depth is measured by the distance from the root node. We are given the root of the binary tree and a positive integer k, and we need to return the kth largest value among all level sums.
If the tree doesn't have k levels, we must return -1. This problem emphasizes that the notion of level is based on a node's distance from the root, meaning that all nodes at the same distance (or depth) from the root are on the same level.
Flowchart Walkthrough
Let's analyze the problem using the Flowchart step by step to determine the appropriate algorithm for LeetCode 2583. Kth Largest Sum in a Binary Tree:
Is it a graph?
- Yes: A binary tree is a special case of a graph where each node has at most two children.
Is it a tree?
- Yes: A binary tree is by definition a tree.
Does the problem relate to directed acyclic graphs (DAGs)?
- No: We are dealing with a binary tree structure, not a general directed acyclic graph.
Does the problem involve shortest paths?
- No: The task is to find the kth largest sum path, not the shortest path between nodes.
Does the problem involve connectivity?
- No: The problem isn't about finding connected components but rather paths and their sums.
Is the graph weighted?
- Not necessarily stated, but in this context, we're not dealing with graph weights in the conventional sense of shortest path problems. The values of nodes can be considered more as values along a path rather than weights affecting traversal.
Conclusion: Despite not directly leading to BFS, understanding and exploring tree structures often involves BFS for level-order traversal or to explore all possible paths. While the flowchart doesn't point directly to BFS for finding sums of paths, BFS could potentially be used to traverse the tree, visiting all nodes and calculating path sums, especially if combined with a priority queue to track kth largest sums. However, based on the flowchart, the path for BFS isn't explicitly outlined for this specific type of problem without further adaptation or additional context.
Intuition
To solve this problem, we will perform a level-order traversal (also known as breadth-first search) to calculate the sum of each level in the tree. Since we traverse the tree level by level, we can easily compute the sum of the nodes at each depth. The level-order traversal uses a queue to keep track of the nodes as we progress.
Here's the step-by-step approach to arriving at the solution:
- Initialize an empty list
arr
to store the sum of the values at each level and a queueq
initialized with the root node of the tree. - While the queue is not empty, we proceed to the following:
- Initialize a temporary sum
t
to 0 to accumulate the sum of the values for the current level. - For all the nodes in the queue (which are all on the same level):
- Dequeue the node from the front of the queue.
- Add the node's value to
t
. - If the node has a left child, enqueue it to the queue.
- If the node has a right child, enqueue it to the queue.
- After processing all the nodes at the current level, append the sum
t
to the listarr
.
- Initialize a temporary sum
- After the traversal is complete, we use the
nlargest
function from Python's heapq module to fetch the k highest values from the array. The last element in the list returned bynlargest
will be the kth largest value. - Finally, we check if the array contains fewer than k elements. If so, return -1 as there are not enough levels in the tree. Otherwise, we return the last element from the list obtained in the previous step, which is the kth largest level sum.
Following this intuitive approach provides us with a simple and effective solution to identify the kth largest level sum in the given binary tree.
Learn more about Tree, Breadth-First Search and Binary Search patterns.
Solution Approach
The solution follows a breadth-first search (BFS) approach, which is perfectly suited for level-by-level traversal in a binary tree. The key data structures and algorithms used are:
- A
deque
from thecollections
module: It functions as a double-ended queue allowing for efficient insertion and removal from both ends. In our BFS, it's used to enqueue and dequeue nodes. - A list
arr
to keep the sum of values for each level. - The
nlargest
function from Python'sheapq
module: Heaps are used to obtain the largest (or smallest) elements without sorting the entire list, andnlargest
is specifically optimized to find the 'n' largest elements in a dataset.
Here's a detailed breakdown of the implementation:
-
Initialize a list
arr
which will hold the sums of node values at each level and adeque
calledq
with theroot
as the only element. Thedeque
structure allows easy access for enqueueing and dequeueing nodes as we traverse the tree level by level. -
Initiate a
while
loop that continues as long as there are nodes in the queueq
. This loop continues until every node has been visited. -
Inside the loop, set a temporary cumulative sum
t
to zero before considering each level. This is crucial for accumulating the sum of node values at the current level. -
Execute another loop over
q
for the number of nodes at the current level (determined bylen(q)
). Here are the key steps within this loop:- Dequeue (
popleft()
) the current node fromq
and add its value to the temporary sumt
. - Check if the current node has a left child (
root.left
). If so, enqueue this child node toq
. - Similarly, check for a right child (
root.right
) and enqueue it if present.
- Dequeue (
-
After processing all nodes at the current level, append the level sum
t
to the listarr
. -
Once the while loop is complete (no more nodes to process in the queue), check if we have at least
k
levels by comparing the length ofarr
withk
. -
If there aren't enough levels, we return
-1
as specified. Otherwise, we find the kth largest value in the sums collected by callingnlargest(k, arr)[-1]
. Thenlargest
function constructs a min-heap of thek
largest elements fromarr
and returns them as a list. We are only interested in the kth element, which is the last one in the list returned bynlargest
.
This implementation ensures efficient computation of the solution, leveraging BFS for traversal and a min-heap to effectively get the kth largest value without the need to sort the whole arr
, which could be more expensive in terms of time complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a simple example:
Consider the following binary tree: 5 / \ 3 8 / \ / \ 2 4 6 9 And let k = 2, meaning we want to find the 2nd largest level sum.
-
Initialize a list
arr = []
. Initialize a queueq
and put the root node (value 5) in it. -
Begin the level-order traversal:
-
Level 0 sum: Queue = [5]
- Dequeue 5, add to temporary sum
t = 5
. Enqueue its left (3) and right (8) children. - Level sum = 5, so
arr = [5]
.
- Dequeue 5, add to temporary sum
-
Level 1 sum: Queue = [3, 8]
- Dequeue 3, add to
t = 3
. Enqueue its left (2) and right (4) children. - Dequeue 8, add to
t = 11
. Enqueue its left (6) and right (9) children. - Level sum = 11,
arr = [5, 11]
.
- Dequeue 3, add to
-
Level 2 sum: Queue = [2, 4, 6, 9]
- Dequeue 2, add to
t = 2
. - Dequeue 4, add to
t = 6
. - Dequeue 6, add to
t = 12
. - Dequeue 9, add to
t = 21
. - Level sum = 21,
arr = [5, 11, 21]
.
- Dequeue 2, add to
-
-
After the traversal,
arr = [5, 11, 21]
now contains the level sums. -
We use
nlargest
to fetch the 2 largest values fromarr
:nlargest(2, arr)
gives[21, 11]
. -
Since
arr
contains more thank
elements, we do not return -1. -
Finally, we return the last element in the list returned by
nlargest
which is the 2nd largest value,11
.
By following these steps, we efficiently solve the problem and find the 2nd largest level sum in our example binary tree.
Solution Implementation
1from collections import deque
2import heapq
3
4# Definition for a binary tree node.
5class TreeNode:
6 def __init__(self, val=0, left=None, right=None):
7 self.val = val
8 self.left = left
9 self.right = right
10
11class Solution:
12 def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
13 # This list will contain the sum of node values at each level.
14 level_sums = []
15 # Queue for Breadth First Search (BFS).
16 queue = deque([root])
17
18 # Perform BFS to traverse the tree level by level.
19 while queue:
20 # Temporary variable to keep the sum of the current level's nodes.
21 current_level_sum = 0
22 # Iterate over all nodes at the current level.
23 for _ in range(len(queue)):
24 node = queue.popleft()
25 current_level_sum += node.val
26 # Add left child to the queue if it exists.
27 if node.left:
28 queue.append(node.left)
29 # Add right child to the queue if it exists.
30 if node.right:
31 queue.append(node.right)
32 # Append the sum of the current level to the list.
33 level_sums.append(current_level_sum)
34
35 # If there are fewer levels than k, return -1 as it's not possible to find the kth largest sum.
36 if len(level_sums) < k:
37 return -1
38 # Use nlargest from heapq to find the kth largest element in the list of level sums.
39 # nlargest(k, level_sums) will return the k largest elements in the list,
40 # and [-1] will get the last element among them, which is the kth largest.
41 return heapq.nlargest(k, level_sums)[-1]
42
1// Class definition for a binary tree node.
2class TreeNode {
3 int val;
4 TreeNode left;
5 TreeNode right;
6
7 // Constructors to initialize tree nodes.
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
17class Solution {
18 // Finds the kth largest level sum in a binary tree.
19 public long kthLargestLevelSum(TreeNode root, int k) {
20 // List to record the sum of values at each level.
21 List<Long> levelSums = new ArrayList<>();
22
23 // Queue to perform level order traversal of the tree.
24 Deque<TreeNode> queue = new ArrayDeque<>();
25
26 // Start with the root node.
27 queue.offer(root);
28
29 // Perform level order traversal to calculate level sums.
30 while (!queue.isEmpty()) {
31 long levelSum = 0;
32
33 // Iterate over all nodes at the current level.
34 for (int count = queue.size(); count > 0; --count) {
35 TreeNode currentNode = queue.pollFirst();
36
37 // Accumulate the values of the nodes at this level.
38 levelSum += currentNode.val;
39
40 // Add child nodes for the next level.
41 if (currentNode.left != null) {
42 queue.offer(currentNode.left);
43 }
44 if (currentNode.right != null) {
45 queue.offer(currentNode.right);
46 }
47 }
48
49 // Store the level sum.
50 levelSums.add(levelSum);
51 }
52
53 // If there are fewer levels than k, return -1.
54 if (levelSums.size() < k) {
55 return -1;
56 }
57
58 // Sort the sums in descending order to find the kth largest sum.
59 Collections.sort(levelSums, Collections.reverseOrder());
60
61 // Return the kth element in the sorted list, adjusting the index as list is 0-based.
62 return levelSums.get(k - 1);
63 }
64}
65
1#include <algorithm>
2#include <queue>
3#include <vector>
4
5// Definition for a binary tree node.
6struct TreeNode {
7 int val;
8 TreeNode *left;
9 TreeNode *right;
10 TreeNode() : val(0), left(nullptr), right(nullptr) {}
11 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17 // Function to find the kth largest sum of a level in a binary tree.
18 long long kthLargestLevelSum(TreeNode* root, int k) {
19 // Initialize a vector to store the sum of each level.
20 std::vector<long long> levelSums;
21
22 // Queue for level order traversal.
23 std::queue<TreeNode*> queue;
24 queue.push(root);
25
26 // Perform level order traversal to calculate the sum of each level.
27 while (!queue.empty()) {
28 // Temporary variable to hold the sum of the current level.
29 long long sumOfCurrentLevel = 0;
30
31 // Go through all nodes at the current level.
32 for (int levelSize = queue.size(); levelSize > 0; --levelSize) {
33 // Get the next node in the queue.
34 root = queue.front();
35 queue.pop();
36
37 // Add the node's value to the sum of the current level.
38 sumOfCurrentLevel += root->val;
39
40 // Add left and right children if they exist.
41 if (root->left) {
42 queue.push(root->left);
43 }
44 if (root->right) {
45 queue.push(root->right);
46 }
47 }
48
49 // Store the sum of the current level in the vector.
50 levelSums.push_back(sumOfCurrentLevel);
51 }
52
53 // If there are fewer levels than k, return -1 as it's not possible to find the kth largest level sum.
54 if (levelSums.size() < k) {
55 return -1;
56 }
57
58 // Sort the vector in descending order to find the kth largest level sum.
59 std::sort(levelSums.rbegin(), levelSums.rend());
60
61 // Return the kth largest level sum.
62 return levelSums[k - 1];
63 }
64};
65
1// Represents a node in a binary tree with a value, and left and right children
2class TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6 constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
7 this.val = val === undefined ? 0 : val;
8 this.left = left === undefined ? null : left;
9 this.right = right === undefined ? null : right;
10 }
11}
12
13/**
14 * Finds the kth largest sum of values at each level of a binary tree.
15 * @param {TreeNode | null} root - Root node of a binary tree.
16 * @param {number} k - The kth largest element to find in the level sums.
17 * @return {number} - The kth largest level sum, or -1 if there are less than k levels.
18 */
19function kthLargestLevelSum(root: TreeNode | null, k: number): number {
20 // Array to store the sum of values at each level of the tree
21 const levelSums: number[] = [];
22
23 // Queue for breadth-first traversal, starting with the root node
24 const queue: Array<TreeNode | null> = [root];
25
26 // Traverse the tree by levels
27 while (queue.length) {
28 let levelSum = 0; // Sum of values at the current level
29 const levelSize = queue.length;
30
31 // Process each node at the current level
32 for (let i = 0; i < levelSize; ++i) {
33 const currentNode = queue.shift();
34 if (currentNode) {
35 // Add the value of the current node to the level sum
36 levelSum += currentNode.val;
37 // Add the left child to the queue if it exists
38 if (currentNode.left) {
39 queue.push(currentNode.left);
40 }
41 // Add the right child to the queue if it exists
42 if (currentNode.right) {
43 queue.push(currentNode.right);
44 }
45 }
46 }
47
48 // Store the sum of the current level
49 levelSums.push(levelSum);
50 }
51
52 // If there are fewer levels than k, return -1
53 if (levelSums.length < k) {
54 return -1;
55 }
56
57 // Sort the sums in descending order to find the kth largest
58 levelSums.sort((a, b) => b - a);
59
60 // Return the kth largest level sum
61 return levelSums[k - 1];
62}
63
Time and Space Complexity
The time complexity of the given code is O(N + klogN)
, where N
is the number of nodes in the binary tree. The O(N)
term comes from the BFS traversal of the tree, which processes each node once. The O(klogN)
term comes from finding the k-th largest sum using the nlargest
function from the heap module, which is typically implemented as a heap-based selection algorithm with that complexity.
The space complexity is O(N)
, as the queue q
can contain at most all the nodes of the last level in the worst case (considering a complete binary tree), and the array arr
will also contain a sum for each level of the tree, which can be at most N
if the tree is skewed (i.e., each level contains only one node).
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
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 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
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Want a Structured Path to Master System Design Too? Donāt Miss This!