Kth Largest Sum In A Binary Tree - Leetcode Solution

Problem Statement:

Given a binary tree, write a function to find the kth largest sum of the subtree values in the tree.

Solution:

This problem can be solved by first calculating the sum of all the subtrees in the binary tree and storing them in an array. Then we can sort the array in decreasing order and return the kth element in the array.

To calculate the sum of all the subtrees, we can use a recursive function that traverses the entire binary tree and calculates the sum of all the nodes in each subtree. We can store these sums in an array and return the sorted array.

The time complexity of this solution is O(n log n), where n is the number of nodes in the binary tree. This is due to the sorting of the array.

Implementation:

Here is the implementation of the solution in Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthLargestSum(root: TreeNode, k: int) -> int:
    sums = []
    
    def get_subtree_sum(node):
        if not node:
            return 0
        left_sum = get_subtree_sum(node.left)
        right_sum = get_subtree_sum(node.right)
        total_sum = left_sum + right_sum + node.val
        sums.append(total_sum)
        return total_sum
    
    get_subtree_sum(root)
    sums.sort(reverse=True)
    return sums[k-1]

In this implementation, we define a TreeNode class to represent the nodes of the binary tree, and a function kthLargestSum that takes a TreeNode object and an integer k as input and returns the kth largest sum of the subtree values in the tree.

The get_subtree_sum function is a recursive helper function that calculates the sum of all the nodes in each subtree and appends it to the sums array.

Finally, we sort the sums array in descending order and return the kth element in the array (indexed as k-1).

Example:

Let's test our solution on the following binary tree:

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

We can represent this binary tree using TreeNode objects as follows:

root = TreeNode(1,
    TreeNode(2,
        TreeNode(4),
        TreeNode(5)
    ),
    TreeNode(3,
        TreeNode(6),
        TreeNode(7)
    )
)

If we call kthLargestSum on this tree with k=2, we should get the second largest sum of the subtree values in the tree.

print(kthLargestSum(root, 2))  # Output: 16

The sum of all the subtrees in the tree are:

[28, 14, 14, 6, 5, 3, 4, 1]

And the second largest sum is 16.

1