Kth Largest Perfect Binary Subtree
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Kth Largest Perfect Binary Subtree
A **perfect binary tree** is a binary tree in which every internal node has exactly two children and all leaf nodes lie at the same depth. A single node (a leaf) is itself a perfect binary tree of height $0$ containing one node, and a perfect binary tree of height $h$ contains exactly $2^{h+1} - 1$ nodes.
You are given the root of a binary tree and an integer `k`. For every node `u` in the tree, decide whether the subtree rooted at `u` is a perfect binary tree. Collect the **sizes** (node counts) of all such perfect subtrees into a multiset — each qualifying node contributes one value, even when several subtrees have the same size.
Return the size of the **k-th largest** perfect binary subtree: that is, the `k`-th element when these sizes are listed in non-increasing order. If fewer than `k` nodes root a perfect binary subtree, return `-1`.
Notes:
- "Largest" is measured by node count, not by node value. Node values do not affect whether a subtree is perfect.
- A subtree rooted at `u` is perfect if and only if `u` is a leaf, or both of `u`'s children exist, the left and right subtrees have equal height, and each of them is itself perfect.
## Input format
- `root`: the binary tree given in level-order (breadth-first) as an array, using `null` for absent children. Node values are integers.
- `k`: a 1-indexed positive integer.
## Output format
- A single integer: the node count of the `k`-th largest perfect binary subtree, or `-1` if there are fewer than `k` of them.
## Examples
**Example 1**
```
Input: root = [3, 9, 20, null, null, 15, 7], k = 1
Output: 3
```
The perfect subtrees are: the node `20` (its children `15` and `7` are leaves at equal depth) with size `3`, and the three leaves `9`, `15`, `7` with size `1` each. Sizes sorted non-increasingly are `[3, 1, 1, 1]`, so the 1st largest is `3`.
**Example 2**
```
Input: root = [3, 9, 20, null, null, 15, 7], k = 2
Output: 1
```
Using the multiset `[3, 1, 1, 1]`, the 2nd largest value is `1`.
**Example 3**
```
Input: root = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: 3
```
The whole tree is perfect (size `7`); nodes `2` and `3` each root a perfect subtree of size `3`; the four leaves each have size `1`. Sorted non-increasingly: `[7, 3, 3, 1, 1, 1, 1]`. The 3rd largest is `3`.
**Example 4**
```
Input: root = [1, 2, 3, null, null, 6, 7], k = 5
Output: -1
```
Perfect subtrees: node `3` (size `3`) and leaves `2`, `6`, `7` (size `1` each) — only `4` qualifying subtrees, so there is no 5th.
## Constraints
- The number of nodes `n` satisfies $1 \le n \le 10^5$.
- $1 \le k \le n$ is not guaranteed; `k` may exceed the number of perfect subtrees, in which case return `-1`.
- Node values fit in a signed 32-bit integer.
Quick Answer: This question evaluates a candidate's ability to combine tree traversal with structural validation, requiring recognition of perfect binary subtrees and aggregation of their sizes. It tests recursive height/size computation and order-statistic selection over tree-derived data, commonly asked to gauge practical coding skill in tree-based algorithm problems.
A **perfect binary tree** is a binary tree in which every internal node has exactly two children and all leaf nodes lie at the same depth. A single node (a leaf) is a perfect binary tree of height 0 containing one node; a perfect binary tree of height h contains exactly 2^(h+1) - 1 nodes.
You are given the root of a binary tree (as a level-order / breadth-first array, using `null` for absent children) and an integer `k`. For every node `u`, decide whether the subtree rooted at `u` is a perfect binary tree. Collect the **sizes** (node counts) of all such perfect subtrees into a multiset — each qualifying node contributes one value, even when several subtrees have the same size.
Return the size of the **k-th largest** perfect binary subtree (the k-th element when the sizes are listed in non-increasing order). If fewer than `k` nodes root a perfect binary subtree, return `-1`.
A subtree rooted at `u` is perfect iff `u` is a leaf, or both children exist, the left and right subtrees have equal height, and each of them is itself perfect. "Largest" is measured by node count, not by node value.
Example: root = [3, 9, 20, null, null, 15, 7], k = 1 -> 3. The perfect subtrees are node 20 (size 3) and the leaves 9, 15, 7 (size 1 each); sizes non-increasing are [3, 1, 1, 1], so the 1st largest is 3.
Constraints
- 1 <= n <= 10^5 (number of nodes).
- k is a 1-indexed positive integer; k may exceed the number of perfect subtrees, in which case return -1.
- Node values fit in a signed 32-bit integer and do not affect whether a subtree is perfect.
- The tree is given in level-order (BFS) form with null for absent children.
Examples
Input: ([3, 9, 20, None, None, 15, 7], 1)
Expected Output: 3
Explanation: Perfect subtrees: node 20 (size 3) and leaves 9, 15, 7 (size 1 each). Sorted non-increasingly: [3, 1, 1, 1]; the 1st largest is 3.
Input: ([3, 9, 20, None, None, 15, 7], 2)
Expected Output: 1
Explanation: Same multiset [3, 1, 1, 1]; the 2nd largest value is 1.
Input: ([1, 2, 3, 4, 5, 6, 7], 3)
Expected Output: 3
Explanation: The whole tree is perfect (size 7); nodes 2 and 3 each root a perfect subtree of size 3; four leaves have size 1. Sorted: [7, 3, 3, 1, 1, 1, 1]; the 3rd largest is 3.
Input: ([1, 2, 3, None, None, 6, 7], 5)
Expected Output: -1
Explanation: Perfect subtrees: node 3 (size 3) and leaves 2, 6, 7 (size 1 each) — only 4 qualify, so there is no 5th.
Input: ([1], 1)
Expected Output: 1
Explanation: A single node is a perfect subtree of size 1; the 1st largest is 1.
Input: ([-5], 2)
Expected Output: -1
Explanation: Only one perfect subtree (the single node), so there is no 2nd; node value being negative does not matter.
Input: ([1, 2, 3, 4, 5, 6, 7], 1)
Expected Output: 7
Explanation: The full 7-node tree is perfect, so the largest perfect subtree size is 7.
Input: ([1, 2, 3, 4, None, None, 7], 1)
Expected Output: 1
Explanation: Node 2 has only a left child and node 3 only a right child, so neither is perfect; the root's children have unequal height too. Only the leaves 4 and 7 qualify (size 1 each), so the largest is 1.
Hints
- Do a single post-order (bottom-up) traversal. For each node compute three things at once: whether its subtree is perfect, its height, and its node count.
- A node's subtree is perfect exactly when both children's subtrees are perfect AND their heights are equal (a leaf has both empty children of height -1, which are equal, so a leaf is perfect).
- Collect the size of every perfect subtree into a list. If only the root is perfect you still count every internal perfect subtree separately.
- Sort the collected sizes in non-increasing order and return the (k-1)-th entry; if the list has fewer than k entries, return -1.