Skip to main content
Talentd

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

MediumTreeDepth-First SearchSortingBinary Tree18 min readAsked at: Google
Practice this problem

Problem Statement

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the kth largest perfect binary subtree, or -1 if it doesn't exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

 

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in non-increasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

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

Output: -1

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 2000].
  • 1 <= Node.val <= 2000
  • 1 <= k <= 1024

Approach Overview

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.

Approach 1: Post-order Traversal with Size Calculation

This approach involves performing a post-order traversal of the binary tree. For each node, determine if its subtrees form a perfect binary tree. If they do, calculate its size.

In post-order traversal, we recursively visit the left subtree, then the right subtree, and finally process the root node. By checking the height and size of left and right subtrees, we can ascertain if a node is the root of a perfect subtree.

Collect all valid subtree sizes and retrieve the k-th largest using sorting.

The function countPerfectSubtreeSizes utilizes a recursive helper function post_order, which traverses the tree and accumulates the sizes of perfect subtrees in a list. The tree's perfect subtree sizes are calculated using the condition that both left and right subtrees are perfect and have equal heights.

Code

PythonJavaC++C#JavaScriptC

Python

Java

C++

C#

JavaScript

C

Complexity

Time Complexity: O(n log n), where n is the number of nodes in the tree. The traversal takes O(n) and sorting the subtree sizes takes O(log n).

Space Complexity: O(n), for storing the sizes of perfect subtrees.

Try this approach in the editor →

Approach 2: DFS + Sorting

We define a function dfs to calculate the size of the perfect binary subtree rooted at the current node, using an array nums to record the sizes of all perfect binary subtrees. If the subtree rooted at the current node is not a perfect binary subtree, it returns -1.

The execution process of the function dfs is as follows:

  1. If the current node is null, return 0;
  2. Recursively calculate the sizes of the perfect binary subtrees of the left and right subtrees, denoted as l and r respectively;
  3. If the sizes of the left and right subtrees are not equal, or if the sizes of the left and right subtrees are less than 0, return -1;
  4. Calculate the size of the perfect binary subtree rooted at the current node cnt = l + r + 1, and add cnt to the array nums;
  5. Return cnt.

We call the dfs function to calculate the sizes of all perfect binary subtrees. If the length of the array nums is less than k, return -1. Otherwise, sort the array nums in descending order and return the k-th largest perfect binary subtree size.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Post-order Traversal with Size Calculation

Time Complexity: O(n log n), where n is the number of nodes in the tree. The traversal takes O(n) and sorting the subtree sizes takes O(log n).

Space Complexity: O(n), for storing the sizes of perfect subtrees.

DFS + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Post-order DFS + Collect Sizes + SortO(n log n)O(n)Best for clarity and typical interview constraints where storing all subtree sizes is acceptable.
Post-order DFS + Min Heap of Size kO(n log k)O(k)Useful when the tree is large but only the k-th largest value matters.

Video Solution

K-th Largest Perfect Subtree Size in Binary Tree || LeetCode Weekly Contest 419 || Leetcode Solution • codi • 547 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is K-th Largest Perfect Subtree Size in Binary Tree easy or hard?
The problem is generally rated Medium because it combines multiple concepts: recognizing perfect subtree conditions, implementing post-order DFS, and selecting the k-th largest value. The logic is manageable once you realize the subtree validity must be determined bottom-up.
K-th Largest Perfect Subtree Size in Binary Tree Python/Java solution
The implementation is nearly identical across Python, Java, C++, C#, JavaScript, and C. A recursive DFS returns subtree height when the subtree is perfect. When both children return equal heights, compute the subtree size and store it. After traversal, sort the sizes or maintain a heap to extract the k-th largest.
How to solve K-th Largest Perfect Subtree Size in Binary Tree in O(n)?
The subtree validation itself runs in O(n) using a single post-order DFS. Each node returns the height of its subtree if it is perfect, or -1 otherwise. Perfect subtree sizes are computed during traversal. If only detection is required the algorithm is O(n); retrieving the k-th largest requires either sorting or a heap on top of that traversal.
What is the best approach for K-th Largest Perfect Subtree Size in Binary Tree?
The best approach uses post-order depth-first search to evaluate subtree properties bottom-up. Each node checks whether its left and right subtrees are perfect and have the same height. If they do, the subtree is perfect and its size is recorded. After collecting sizes, either sort them or maintain a min-heap to retrieve the k-th largest value.
Is K-th Largest Perfect Subtree Size in Binary Tree asked at Google/Amazon/Meta?
Binary tree DFS problems that evaluate subtree properties are common in interviews at companies like Google, Amazon, and Meta. Variants include checking balanced trees, computing subtree sizes, or validating structural constraints. This problem tests similar bottom-up reasoning using post-order traversal.
What data structure is used in K-th Largest Perfect Subtree Size in Binary Tree?
The solution primarily uses a binary tree traversal with recursion (DFS). An auxiliary list or a min-heap is used to store sizes of perfect subtrees. The heap variant helps efficiently track the k-th largest value without sorting all results.
What is the time complexity of K-th Largest Perfect Subtree Size in Binary Tree?
The DFS traversal visits each node once, giving O(n) base complexity. If you store all perfect subtree sizes and sort them, the total complexity becomes O(n log n). Using a min-heap of size k improves it to O(n log k) while keeping the same O(n) traversal cost.

Ready to solve this problem?

Practice K-th Largest Perfect Subtree Size in Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Balanced Binary Tree