Problem statement

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

A subtree (a node with all of its descendants) is perfect when every one of its leaves is at the same depth and every one of its other nodes has exactly two children. A single leaf is a perfect subtree of size 1.

List the sizes (node counts) of all the perfect subtrees, one entry per subtree, in non-increasing order, and return the k-th entry. If there are fewer than k perfect subtrees, return -1.

Example 1

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2
Output: 3
Explanation: Each 5 on the third level forms a perfect subtree of 3 nodes with its two leaf children, and each of the six leaves is one of size 1. In decreasing order 3, 3, 1, …: the second is 3.

Example 2

Input: root = [1,2,3,4,5,6,7], k = 1
Output: 7
Explanation: The whole tree is perfect, 7 nodes.

Example 3

Input: root = [1,2,3,null,4], k = 3
Output: -1
Explanation: Only the two leaves 4 and 3 are perfect subtrees, so there is no third.

Constraints

• 1 <= number of nodes <= 2000
• 1 <= Node.val <= 2000
• 1 <= k <= 1024

Hints for K-th Largest Perfect Subtree Size in Binary Tree

1. Hint 1

   A subtree is perfect exactly when both child subtrees are perfect and have the same height. An empty child counts as perfect of height 0.

2. Hint 2

   So a post-order function can return the height of a perfect subtree, or −1 when the subtree is not perfect.

3. Hint 3

   A perfect subtree of height h has 2^h − 1 nodes. Collect those sizes, sort them in decreasing order and read the k-th.

How to solve K-th Largest Perfect Subtree Size in Binary Tree

Decide perfection bottom-up: a node roots a perfect subtree of height h + 1 when both children root perfect subtrees of the same height h. Every such node contributes one size 2^(h+1) − 1.

Approach

1. Define height(node): 0 for an empty subtree.
2. Compute l = height(left) and r = height(right). If either is −1 or l != r, return −1.
3. Otherwise the node roots a perfect subtree of height l + 1: record its size 2^(l+1) − 1 and return l + 1.
4. Sort the recorded sizes in decreasing order; return the k-th, or −1 if there are fewer than k.

Why it works

If both children are perfect with the same height, all leaves of the node's subtree are at one depth and every internal node has two children (the node itself has two non-empty children, or none when l = r = 0 — a leaf). If the heights differ or a child is not perfect, the leaf depths differ or some node lacks a child, so the subtree is not perfect. Each perfect subtree is recorded exactly once, at its root.

Complexity

• Time — O(n log n) — dominated by the sort
• Space — O(n)

Pitfalls

• Equal subtree sizes are separate entries in the ranking, not merged.
• A node with exactly one child is never perfect, even if that child is.

Reference solution

Python

from typing import Optional

def kthLargestPerfectSubtree(root: Optional[TreeNode], k: int) -> int:
    sizes = []

    def height(node):
        if node is None:
            return 0
        l = height(node.left)
        r = height(node.right)
        if l < 0 or r < 0 or l != r:
            return -1
        sizes.append((1 << (l + 1)) - 1)
        return l + 1

    height(root)
    if len(sizes) < k:
        return -1
    sizes.sort(reverse=True)
    return sizes[k - 1]

Java

public static int kthLargestPerfectSubtree(TreeNode root, int k) {
    List<Integer> sizes = new ArrayList<>();
    perfectHeight(root, sizes);
    if (sizes.size() < k) return -1;
    sizes.sort(Collections.reverseOrder());
    return sizes.get(k - 1);
}

static int perfectHeight(TreeNode node, List<Integer> sizes) {
    if (node == null) return 0;
    int l = perfectHeight(node.left, sizes), r = perfectHeight(node.right, sizes);
    if (l < 0 || r < 0 || l != r) return -1;
    sizes.add((1 << (l + 1)) - 1);
    return l + 1;
}

C++

static int perfectHeight(TreeNode* node, vector<int>& sizes);

int kthLargestPerfectSubtree(TreeNode* root, int k) {
    vector<int> sizes;
    perfectHeight(root, sizes);
    if ((int) sizes.size() < k) return -1;
    sort(sizes.rbegin(), sizes.rend());
    return sizes[k - 1];
}

static int perfectHeight(TreeNode* node, vector<int>& sizes) {
    if (!node) return 0;
    int l = perfectHeight(node->left, sizes), r = perfectHeight(node->right, sizes);
    if (l < 0 || r < 0 || l != r) return -1;
    sizes.push_back((1 << (l + 1)) - 1);
    return l + 1;
}

JavaScript

var kthLargestPerfectSubtree = function(root, k) {
    var sizes = [];
    var height = function(node) {
        if (node === null) return 0;
        var l = height(node.left), r = height(node.right);
        if (l < 0 || r < 0 || l !== r) return -1;
        sizes.push((1 << (l + 1)) - 1);
        return l + 1;
    };
    height(root);
    if (sizes.length < k) return -1;
    sizes.sort(function(a, b) { return b - a; });
    return sizes[k - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium
• Sum of Nodes on the Longest Path from Root to Leaf Medium