2583. Kth Largest Sum in a Binary Tree

[mah-shamim]

Discussed in https://github.com/mah-shamim/leet-code-in-php/discussions/735

^{Originally posted by **mah-shamim** October 22, 2024} **Topics:** `Tree`, `Breadth-First Search`, `Sorting`, `Binary Tree` You are given the `root` of a binary tree and a positive integer `k`. The **level sum** in the tree is the sum of the values of the nodes that are on the **same** level. Return _the kth **largest** level sum in the tree (not necessarily distinct)_. If there are fewer than `k` levels in the tree, return _`-1`_. **Note** that two nodes are on the same level if they have the same distance from the root. **Example 1:**  - **Input:** root = [5,8,9,2,1,3,7,4,6], k = 2 - **Output:** 13 - **Explanation:** The level sums are the following: - Level 1: 5. - Level 2: 8 + 9 = 17. - Level 3: 2 + 1 + 3 + 7 = 13. - Level 4: 4 + 6 = 10. The 2^nd largest level sum is 13. **Example 2:**  - **Input:** root = [1,2,null,3], k = 1 - **Output:** 3 - **Explanation:** The largest level sum is 3. **Constraints:** - The number of nodes in the tree is `n`. - 2 <= n <= 105 - 1 <= Node.val <= 106 - `1 <= k <= n` **Hint:** 1. Find the sum of values of nodes on each level and return the kth largest one. 2. To find the sum of the values of nodes on each level, you can use a DFS or BFS algorithm to traverse the tree and keep track of the level of each node.

[mah-shamim]

We'll follow these steps:

1. Level Order Traversal: We will use a Breadth-First Search (BFS) to traverse the tree level by level.
2. Calculate Level Sums: During the BFS traversal, we'll calculate the sum of node values at each level.
3. Sort and Find k-th Largest Sum: After calculating the sums for all levels, we'll sort the sums and retrieve the k-th largest value.

Let's implement this solution in PHP: 2583. Kth Largest Sum in a Binary Tree

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val;
    public $left;
    public $right;
    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @param Integer $k
 * @return Integer
 */
function kthLargestLevelSum($root, $k) {
    if ($root === null) {
        return -1;
    }

    // Use BFS to traverse the tree level by level
    $queue = [];
    array_push($queue, $root);
    $levelSums = [];

    // BFS loop
    while (!empty($queue)) {
        $levelSize = count($queue);
        $currentLevelSum = 0;

        // Process each node in the current level
        for ($i = 0; $i < $levelSize; $i++) {
            $node = array_shift($queue);
            $currentLevelSum += $node->val;

            // Add left and right children to the queue for the next level
            if ($node->left !== null) {
                array_push($queue, $node->left);
            }
            if ($node->right !== null) {
                array_push($queue, $node->right);
            }
        }

        // Store the sum of the current level
        array_push($levelSums, $currentLevelSum);
    }

    // Sort the level sums in descending order
    rsort($levelSums);

    // Return the k-th largest level sum
    return isset($levelSums[$k - 1]) ? $levelSums[$k - 1] : -1;
}

// Example 1:
// Input: root = [5,8,9,2,1,3,7,4,6], k = 2
$root1 = new TreeNode(5);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(9);
$root1->left->left = new TreeNode(2);
$root1->left->right = new TreeNode(1);
$root1->right->left = new TreeNode(3);
$root1->right->right = new TreeNode(7);
$root1->left->left->left = new TreeNode(4);
$root1->left->left->right = new TreeNode(6);
echo kthLargestLevelSum($root1, 2); // Output: 13

// Example 2:
// Input: root = [1,2,null,3], k = 1
$root2 = new TreeNode(1);
$root2->left = new TreeNode(2);
$root2->left->left = new TreeNode(3);
echo kthLargestLevelSum($root2, 1); // Output: 3
?>

Explanation:

1. TreeNode Class: We define the TreeNode class to represent a node in the binary tree, where each node has a value (val), a left child (left), and a right child (right).

2. BFS Traversal: The function kthLargestLevelSum uses a queue to perform a BFS traversal. For each level, we sum the values of the nodes and store the result in an array ($levelSums).

3. Sorting Level Sums: After traversing the entire tree and calculating the level sums, we sort the sums in descending order using rsort. This allows us to easily access the k-th largest sum.

4. Edge Case Handling: If there are fewer than k levels, we return -1.

Time Complexity:

• BFS Traversal: O(n), where n is the number of nodes in the tree.
• Sorting: O(m log m), where m is the number of levels in the tree. Since m is much smaller than n, sorting is relatively fast.
• Overall time complexity: O(n + m log m).

Space Complexity:

• Queue: O(n), for storing nodes during BFS.
• Level Sums: O(m), for storing the sum of each level.
• Overall space complexity: O(n).

This approach ensures that we traverse the tree efficiently and return the correct k^th largest level sum.