Kth Largest Perfect Subtree Size in Binary Tree

medium tree dfs sorting

Problem

Given the root of a binary tree and an integer k, return the size of the kth largest perfect subtree, or -1 if there are fewer than k perfect subtrees. A perfect binary tree is one where every internal node has two children and all leaves are at the same level; its size is its node count.

Inputroot = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output3

The perfect subtree sizes are [3,3,1,1,1,1,1,1]; sorted descending the 2nd largest is 3.

level-order (use "null" for missing children)

def kth_largest_perfect_subtree(root, k):
    sizes = []
    def dfs(node):
        if not node:
            return 0
        L = dfs(node.left)
        R = dfs(node.right)
        if L < 0 or R < 0 or L != R:
            return -1
        size = L + R + 1
        sizes.append(size)
        return size
    dfs(root)
    sizes.sort(reverse=True)
    return sizes[k - 1] if k <= len(sizes) else -1

function kthLargestPerfectSubtree(root, k) {
  const sizes = [];
  function dfs(node) {
    if (!node) return 0;
    const L = dfs(node.left);
    const R = dfs(node.right);
    if (L < 0 || R < 0 || L !== R) return -1;
    const size = L + R + 1;
    sizes.push(size);
    return size;
  }
  dfs(root);
  sizes.sort((a, b) => b - a);
  return k <= sizes.length ? sizes[k - 1] : -1;
}

import java.util.*;
class Solution {
    List<Integer> sizes = new ArrayList<>();
    public int kthLargestPerfectSubtree(TreeNode root, int k) {
        dfs(root);
        sizes.sort(Collections.reverseOrder());
        return k <= sizes.size() ? sizes.get(k - 1) : -1;
    }
    int dfs(TreeNode node) {
        if (node == null) return 0;
        int L = dfs(node.left), R = dfs(node.right);
        if (L < 0 || R < 0 || L != R) return -1;
        int size = L + R + 1;
        sizes.add(size);
        return size;
    }
}

class Solution {
public:
    vector<int> sizes;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int L = dfs(node->left), R = dfs(node->right);
        if (L < 0 || R < 0 || L != R) return -1;
        int size = L + R + 1;
        sizes.push_back(size);
        return size;
    }
    int kthLargestPerfectSubtree(TreeNode* root, int k) {
        dfs(root);
        sort(sizes.rbegin(), sizes.rend());
        return k <= (int) sizes.size() ? sizes[k - 1] : -1;
    }
};

Explanation

A subtree is perfect only if both of its children are themselves perfect and have exactly the same height. We can capture both conditions with a single bottom-up DFS that returns the subtree size, or a sentinel -1 when the subtree is not perfect.

For a node we recurse into the left and right children first. An empty child returns 0 (a perfect tree of size 0). If either child reports -1, or the two child sizes differ, this node cannot be perfect, so it returns -1.

When the two children are perfect and equal in size, the current subtree is also perfect with size L + R + 1. We record that size in a list. Equal child sizes guarantee equal heights here because a perfect tree's size determines its height uniquely.

After the traversal we have every perfect subtree size. Sort them in descending order and return the kth one, or -1 if fewer than k exist.

Example on the sample tree: the recorded sizes are [3,3,1,1,1,1,1,1] (single leaves are perfect size-1 trees, plus two perfect size-3 subtrees). Sorted descending, the 2nd largest is 3.

Time: O(n log n) Space: O(n)