Katkat
Back

Kth Largest Perfect Binary Subtree

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests tree traversal techniques, the ability to validate binary tree properties recursively, and the use of selection algorithms to find order statistics.

Problem Statement

A Perfect Binary Tree is a binary tree in which all interior nodes have two children and all leaves have the same depth. Given the root of a binary tree, identify all subtrees that are perfect binary trees and return the size (total number of nodes) of the Kth largest perfect binary tree found.

If there are fewer than K perfect binary trees, return -1. If multiple subtrees have the same size, count each occurrence separately.

Function Signature

def kth_largest_perfect_subtree(root: TreeNode, k: int) -> int:

Examples

Example 1: Input: root = [1, 2, 3, 4, 5, 6, 7], k = 2 Output: 3 Explanation: The tree is a perfect binary tree of size 7. The subtrees rooted at 2 and 3 are perfect binary trees of size 3. The subtrees rooted at 4, 5, 6, and 7 are perfect binary trees of size 1. The sizes are [7, 3, 3, 1, 1, 1, 1]. The 2nd largest is 3.

Constraints

  • The number of nodes in the tree is in the range [1, 1000].
  • Node values are between -1000 and 1000.
  • 1 <= k <= (Total number of nodes).

Considerations

  • A node with no children is a perfect binary tree of size 1.
  • A node with only one child is not a perfect binary tree.

Hints

Hint 1

Use a post-order traversal to determine if a node's subtree is perfect by comparing the height and size of its left and right children.

Hint 2

A tree is perfect if both children are roots of perfect trees, have the same height, and the current node has both children (or is a leaf).

Hint 3

Collect the sizes of all identified perfect subtrees into a list, sort them in descending order, and return the element at index K-1.

Follow-up questions

  • How would you optimize the space complexity if you only needed the largest perfect subtree size instead of the Kth largest?
  • What changes would be required to identify the largest perfect binary *substructure* that is not necessarily a full subtree rooted at a specific node?
  • How would you handle a scenario where the tree is extremely deep and you want to avoid recursion limit issues?