Kth Largest Sum in a Binary Tree - Practice Coding Problems

Kth Largest Sum in a Binary Tree - Problem

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.

Input & Output

Example 1 — Basic Tree

$ Input: root = [5,8,9,2,1,3,7], k = 2

› Output: 13

💡 Note: Level sums: Level 0 = 5, Level 1 = 8+9 = 17, Level 2 = 2+1+3+7 = 13. Sorted: [17,13,5]. 2nd largest is 13.

Example 2 — Not Enough Levels

$ Input: root = [1,2,null,3], k = 3

› Output: -1

💡 Note: Level sums: Level 0 = 1, Level 1 = 2, Level 2 = 3. Only 3 levels exist, but k=3 asks for 3rd largest. Not enough levels.

Example 3 — Single Node

$ Input: root = [1], k = 1

› Output: 1

💡 Note: Only one level with sum = 1. 1st largest level sum is 1.

Constraints

The number of nodes in the tree is in the range [1, 10⁵]
1 ≤ Node.val ≤ 10⁶
1 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with multiple levels

Level Sums

Calculate sum for each level using BFS

Find Kth Largest

Return kth largest sum or -1 if not enough levels

Key Takeaway

🎯 Key Insight: BFS traversal naturally groups nodes by level, making it perfect for calculating level sums efficiently

Asked in

M Meta 15 a Amazon 12 G Google 8 M Microsoft 6

The key insight is to use BFS to traverse the tree level by level and calculate sums efficiently. Best approach uses BFS + Min-Heap to track only the k largest sums without sorting. Time: O(n + L log k), Space: O(n + k).

Common Approaches

Approach	Time	Space	Notes
✓ BFS + Min-Heap	O(n + L log k)	O(n + k)	Use min-heap of size k to track k largest sums without storing all level sums
BFS + Sort All Sums	O(n + L log L)	O(n + L)	Calculate all level sums using BFS, then sort to find kth largest

BFS + Min-Heap — Algorithm Steps

Step 1: Use BFS to traverse tree level by level
Step 2: For each level sum, add to min-heap of size k
Step 3: If heap size exceeds k, remove smallest element
Step 4: Return top of heap (kth largest) or -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Level Processing

Process each level and calculate sum

Heap Management

Maintain heap of k largest sums

Efficient Result

Top of heap is kth largest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct MinHeap {
    long long* data;
    int size;
    int capacity;
};

struct MinHeap* createHeap(int capacity) {
    struct MinHeap* heap = malloc(sizeof(struct MinHeap));
    heap->data = malloc(capacity * sizeof(long long));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(struct MinHeap* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->data[parent] <= heap->data[index]) break;
        long long temp = heap->data[parent];
        heap->data[parent] = heap->data[index];
        heap->data[index] = temp;
        index = parent;
    }
}

void heapifyDown(struct MinHeap* heap, int index) {
    while (1) {
        int minIndex = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap->size && heap->data[left] < heap->data[minIndex]) {
            minIndex = left;
        }
        if (right < heap->size && heap->data[right] < heap->data[minIndex]) {
            minIndex = right;
        }
        
        if (minIndex == index) break;
        
        long long temp = heap->data[index];
        heap->data[index] = heap->data[minIndex];
        heap->data[minIndex] = temp;
        index = minIndex;
    }
}

void push(struct MinHeap* heap, long long val) {
    heap->data[heap->size] = val;
    heapifyUp(heap, heap->size);
    heap->size++;
}

long long pop(struct MinHeap* heap) {
    long long min = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return min;
}

long long solution(struct TreeNode* root, int k) {
    if (!root) return -1;
    
    struct MinHeap* minHeap = createHeap(k + 1);
    struct TreeNode* queue[10000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int levelsProcessed = 0;
    
    while (front < rear) {
        int levelSize = rear - front;
        long long levelSum = 0;
        
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = queue[front++];
            levelSum += node->val;
            
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        
        levelsProcessed++;
        
        if (minHeap->size < k) {
            push(minHeap, levelSum);
        } else if (levelSum > minHeap->data[0]) {
            pop(minHeap);
            push(minHeap, levelSum);
        }
    }
    
    if (levelsProcessed < k) return -1;
    
    return minHeap->data[0];
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    int k;
    scanf("%d", &k);
    
    printf("-1\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + L log k)

BFS takes O(n) time, heap operations take O(log k) for each of L levels

⚡ Linearithmic

Space Complexity

O(n + k)

BFS queue uses O(n) space, min-heap stores at most k elements

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS + Min-Heap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler