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:

  1. Initialize an empty list arr to store the sum of the values at each level and a queue q initialized with the root node of the tree.
  2. 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 list arr.
  3. 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 by nlargest will be the kth largest value.
  4. 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 the collections 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's heapq module: Heaps are used to obtain the largest (or smallest) elements without sorting the entire list, and nlargest is specifically optimized to find the 'n' largest elements in a dataset.

Here's a detailed breakdown of the implementation:

  1. Initialize a list arr which will hold the sums of node values at each level and a deque called q with the root as the only element. The deque structure allows easy access for enqueueing and dequeueing nodes as we traverse the tree level by level.

  2. Initiate a while loop that continues as long as there are nodes in the queue q. This loop continues until every node has been visited.

  3. 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.

  4. Execute another loop over q for the number of nodes at the current level (determined by len(q)). Here are the key steps within this loop:

    • Dequeue (popleft()) the current node from q and add its value to the temporary sum t.
    • Check if the current node has a left child (root.left). If so, enqueue this child node to q.
    • Similarly, check for a right child (root.right) and enqueue it if present.
  5. After processing all nodes at the current level, append the level sum t to the list arr.

  6. 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 of arr with k.

  7. If there aren't enough levels, we return -1 as specified. Otherwise, we find the kth largest value in the sums collected by calling nlargest(k, arr)[-1]. The nlargest function constructs a min-heap of the k largest elements from arr and returns them as a list. We are only interested in the kth element, which is the last one in the list returned by nlargest.

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 Evaluator

Example 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.
  1. Initialize a list arr = []. Initialize a queue q and put the root node (value 5) in it.

  2. 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].
    • 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].
    • 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].
  3. After the traversal, arr = [5, 11, 21] now contains the level sums.

  4. We use nlargest to fetch the 2 largest values from arr: nlargest(2, arr) gives [21, 11].

  5. Since arr contains more than k elements, we do not return -1.

  6. 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More