K-th Largest Perfect Subtree Size in Binary Tree

K-th Largest Perfect Subtree Size in Binary Tree

1. What is this problem about?

The K-th Largest Perfect Subtree Size interview question asks you to identify and measure "perfect" subtrees. A perfect binary tree is one where all internal nodes have two children and all leaves are at the same level. Your goal is to find all perfect subtrees in a given binary tree, collect their sizes, and return the $k^{th}$ largest size.

2. Why is this asked in interviews?

Google uses this Binary Tree coding problem to test a candidate's ability to propagate multiple pieces of information up a tree. It requires a "bottom-up" recursion that checks for symmetry and depth. It evaluation your proficiency with Depth-First Search (DFS) and sorting statistics derived from a hierarchy.

3. Algorithmic pattern used

This problem follows the Post-order DFS (Bottom-up) pattern.

1. Recursive State: For each node, the DFS should return:
   • Whether the subtree rooted at this node is perfect.
   • The depth of the perfect subtree.
2. Logic: A node forms a perfect subtree if:
   • Both its left and right children are roots of perfect subtrees.
   • Both children have the exact same depth.
3. Collection: Whenever a perfect subtree is identified, its size ($2^{depth+1} - 1$) is added to a list.
4. Final Step: Sort the list of sizes and return the $k^{th}$ largest.

4. Example explanation

Tree: Root 1, Left 2, Right 3.

• Node 2: Leaf. Perfect, depth 0. Size 1.
• Node 3: Leaf. Perfect, depth 0. Size 1.
• Node 1: Left and right are perfect and both depth 0. Node 1 is perfect, depth 1. Size 3. List of sizes: [1, 1, 3]. If $k=1$, result is 3.

5. Common mistakes candidates make

• Pre-order check: Trying to check perfection from the top down, which is $O(N^2)$ because you'd re-visit nodes many times.
• Missing "Perfect" vs "Complete": Perfect trees are more restrictive (all levels full) than complete trees.
• Size calculation: Errors in the $2^h - 1$ formula or forgetting to include the node itself in the count.

6. Interview preparation tip

Practice returning objects or tuples from DFS. Tree problems often require you to know "is valid" and "current height" simultaneously to make a decision for the parent node. This is a core Binary Tree interview pattern.