K-th Largest Perfect Subtree Size in Binary Tree

Naive Approach

The most straightforward approach is to traverse the binary tree and, for each node, check if the subtree rooted at that node is a perfect binary tree. If it is, we calculate its size and store it. After traversing the entire tree, we sort the sizes of the perfect binary trees in non-increasing order and return the k-th largest size.

Code (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_perfect_binary_tree(root):
    if not root:
        return True, 0
    
    def get_height(node):
        if not node:
            return 0
        return 1 + get_height(node.left)

    height = get_height(root)

    def is_perfect(node, h, current_height=1):
        if not node:
            return h == current_height -1

        if not node.left and not node.right:
            return h == current_height

        if not node.left or not node.right:
            return False

        return is_perfect(node.left, h, current_height+1) and is_perfect(node.right, h, current_height+1)

    is_perfect_tree = is_perfect(root, height)
    
    if is_perfect_tree:
        size = 2**height -1
        return True, size
    else:
        return False, 0


def kth_largest_perfect_subtree_naive(root, k):
    sizes = []
    
    def traverse(node):
        if not node:
            return
        
        is_perfect, size = is_perfect_binary_tree(node)
        if is_perfect:
            sizes.append(size)
        
        traverse(node.left)
        traverse(node.right)

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

Time Complexity

• O(N * M), where N is the number of nodes in the tree, and M is the time complexity to check if a subtree is perfect. In the worst case, M can be O(N) if the tree is skewed.
• Sorting the sizes takes O(L log L), where L is the number of perfect binary subtrees.

Space Complexity

• O(N) in the worst case (skewed tree) for the recursion stack.
• O(L) to store the sizes of perfect binary subtrees, where L is the number of such subtrees.

Optimal Approach

To optimize, we can use a bottom-up approach. For each node, we determine if the subtree rooted at that node is a perfect binary tree based on the information from its children. We can calculate the height of the subtree and its size simultaneously. This avoids redundant calculations.

Code (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_largest_perfect_subtree(root, k):
    sizes = []

    def traverse(node):
        if not node:
            return 0, True, 0  # height, is_perfect, size

        left_height, left_perfect, left_size = traverse(node.left)
        right_height, right_perfect, right_size = traverse(node.right)

        if left_perfect and right_perfect and left_height == right_height:
            height = left_height + 1
            size = (1 << height) - 1  # 2**height - 1
            sizes.append(size)
            return height, True, size
        else:
            return -1, False, 0

    traverse(root)
    sizes.sort(reverse=True)

    if k <= len(sizes):
        return sizes[k - 1]
    else:
        return -1

Time Complexity

• O(N), where N is the number of nodes in the tree since we visit each node once.
• Sorting the sizes takes O(L log L), where L is the number of perfect binary subtrees.

Space Complexity

• O(H) for the recursion stack, where H is the height of the tree. In the worst case (skewed tree), H can be O(N).
• O(L) to store the sizes of perfect binary subtrees, where L is the number of such subtrees.

Edge Cases

1. Empty Tree: If the root is None, there are no perfect binary subtrees, so we return -1 if k is greater than 0.
2. k is greater than the number of perfect binary subtrees: If k is larger than the number of perfect binary subtrees, return -1.
3. Tree with only one node: If the tree has only one node, it's a perfect binary tree of size 1. Check if k is 1, and return 1; otherwise, return -1.
4. k is 1: Return the largest perfect binary subtree size.