K-th Largest Perfect Subtree Size in Binary Tree - Solution & Explanation

Problem Overview: You are given the root of a binary tree and an integer k. A subtree is perfect if every internal node has exactly two children and all leaves are at the same depth. The task is to compute the size of every perfect subtree and return the k-th largest size.

The key observation: a subtree is perfect only if both its left and right subtrees are perfect and their heights are equal. That condition is naturally evaluated using depth-first search with a post-order traversal.

Approach 1: Post-order Traversal + Collect and Sort (O(n log n) time, O(n) space)

Traverse the binary tree using post-order DFS. Each recursive call returns the height of the subtree if it is perfect, otherwise a sentinel like -1. When both children return valid heights and those heights are equal, the current subtree is perfect. Its size can be computed using (1 << (height + 1)) - 1 or accumulated from child sizes.

Every time a perfect subtree is detected, append its size to a list. After the DFS finishes, sort the list in descending order using a standard sorting algorithm and return the k-th element if it exists. This approach is straightforward to implement and works well because the DFS visits each node exactly once.

The runtime is O(n) for the traversal plus O(m log m) for sorting, where m is the number of perfect subtrees (worst case n). Space complexity is O(n) due to recursion stack and the array storing subtree sizes.

Approach 2: Post-order Traversal + Min Heap of Size k (O(n log k) time, O(k) space)

The DFS logic for detecting perfect subtrees stays the same. The difference is how you track the k-th largest size. Instead of storing all sizes and sorting later, maintain a min-heap of size at most k. Whenever you discover a perfect subtree, push its size into the heap. If the heap grows beyond k, remove the smallest element.

After processing all nodes, the root of the heap represents the k-th largest perfect subtree size. This reduces memory usage when many perfect subtrees exist and avoids sorting the entire list.

The traversal still costs O(n), and each heap operation costs O(log k). Overall time complexity becomes O(n log k) with O(k) extra space, which is more efficient when k is much smaller than the number of perfect subtrees.

Recommended for interviews: Use the post-order DFS that detects perfect subtrees by comparing left and right heights. Interviewers expect you to recognize that subtree properties must be evaluated bottom-up. Collect-and-sort is simpler and communicates the idea clearly, while the heap optimization shows stronger algorithmic awareness when discussing scalability.