K-th Largest Perfect Subtree Size in Binary Tree

You are given the root of a binary tree and an integer k. Return an integer denoting the size of the k<sup>th</sup> largest perfect binary subtree, or -1 if it doesn't exist. A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Example 1: Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2 Output: 3

Example 2: Input: root = [1,2,3,4,5,6,7], k = 1 Output: 7

Example 3: Input: root = [1,2,3,null,4], k = 3 Output: -1

Given the constraints:

• The number of nodes in the tree is in the range [1, 2000].
• 1 <= Node.val <= 2000
• 1 <= k <= 1024

How would you approach this problem? Write code, analyze the time and space complexity, and consider potential edge cases.

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_size(root, k):
    sizes = []

    def is_perfect(node, depth, level=0):
        if not node:
            return depth == level

        if not node.left and not node.right:
            return depth == level + 1

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

        return is_perfect(node.left, depth, level + 1) and is_perfect(node.right, depth, level + 1)

    def depth(node):
        d = 0
        while (node):
            d += 1
            node = node.left
        return d

    def size(node, perfect_depth):
        if not node:
            return 0
        if not is_perfect(node, perfect_depth):
            return 0
        return 2**perfect_depth - 1

    def traverse(node):
        if not node:
            return

        d = depth(node)
        sz = size(node, d)
        if sz > 0:
            sizes.append(sz)

        traverse(node.left)
        traverse(node.right)

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

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


# Example Usage:
# Create the tree for Example 1
root1 = TreeNode(5)
root1.left = TreeNode(3)
root1.right = TreeNode(6)
root1.left.left = TreeNode(5)
root1.left.right = TreeNode(2)
root1.right.left = TreeNode(5)
root1.right.right = TreeNode(7)
root1.left.left.left = TreeNode(1)
root1.left.left.right = TreeNode(8)
root1.right.right.left = TreeNode(6)
root1.right.right.right = TreeNode(8)

k1 = 2
result1 = kth_largest_perfect_subtree_size(root1, k1)
print(f"The {k1}th largest perfect subtree size is: {result1}")  # Output: 3

# Create the tree for Example 2
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)
root2.left.left = TreeNode(4)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(6)
root2.right.right = TreeNode(7)

k2 = 1
result2 = kth_largest_perfect_subtree_size(root2, k2)
print(f"The {k2}th largest perfect subtree size is: {result2}")  # Output: 7


# Create the tree for Example 3
root3 = TreeNode(1)
root3.left = TreeNode(2)
root3.right = TreeNode(3)
root3.left.right = TreeNode(4)

k3 = 3
result3 = kth_largest_perfect_subtree_size(root3, k3)
print(f"The {k3}th largest perfect subtree size is: {result3}")  # Output: -1

Naive Approach

The naive approach involves traversing the binary tree and, for each node, checking if the subtree rooted at that node is a perfect binary tree. If it is, calculate its size and store it. After traversing the entire tree, sort the sizes in descending order and return the k-th largest size.

Optimal Solution

The provided Python code implements this approach.

1. TreeNode Class: Defines the structure for a binary tree node.
2. kth_largest_perfect_subtree_size(root, k) Function:

   • Initializes an empty list sizes to store the sizes of perfect binary subtrees.

   • is_perfect(node, depth, level=0) Function: Recursively checks if a subtree is a perfect binary tree.

     • It takes a node, the expected depth of the tree, and the current level as input.
     • If the node is None, it checks if the current level matches the expected depth.
     • If the node is a leaf, it checks if the level is one less than the depth.
     • If the node has only one child, it's not a perfect binary tree.
     • Otherwise, it recursively checks if both subtrees are perfect and returns True only if both are.

   • depth(node) Function: Calculates the depth of the binary tree starting from the given node.

   • size(node, perfect_depth) Function: Calculates the size of the subtree if it is perfect.

     • it checks the sizes of perfect binary tree
     • return 0 if it is not a perfect tree
     • otherwise returns the size (2**depth -1)

   • traverse(node) Function:

     • Recursively traverses the binary tree.
     • For each node, it calculates the depth and checks if the subtree rooted at that node is a perfect binary tree.
     • If it's a perfect binary tree, its size is calculated and added to the sizes list.

   • Calls traverse(root) to start the traversal.

   • Sorts the sizes list in descending order.

   • If k is greater than the number of perfect binary subtrees found, it returns -1.

   • Otherwise, it returns the k-th largest size.

Big(O) Runtime Analysis

• depth(node): O(H), where H is the height of the tree.
• is_perfect(node, depth, level): In the worst case, it may visit all nodes in the subtree, which would be O(N) for a complete subtree where N is the number of nodes in the subtree. In a balanced tree, it would be O(log N) for a perfect subtree of size N.
• size(node, perfect_depth): O(1) excluding the is_perfect function call.
• traverse(node): O(n * log n) in the average case, where n is the number of nodes in the tree. For each node, we are calling the is_perfect method that in the worst case is O(log n).
• Sorting sizes: O(m log m), where m is the number of perfect binary subtrees.

Overall, the dominant factor is the tree traversal combined with is_perfect checks, making the time complexity approximately O(n log n) in the average case and O(n^2) in the worst case.

Big(O) Space Usage Analysis

• sizes list: O(m), where m is the number of perfect binary subtrees.
• Recursion stack for traverse: O(H), where H is the height of the tree. In the worst case (skewed tree), H can be N (number of nodes).

Therefore, the space complexity is O(n) in the worst case (skewed tree) and O(log n) in the average case (balanced tree), due to the recursion depth, combined with the space to store the sizes of perfect subtrees.

Edge Cases

1. Empty Tree: If the root is None, the function should return -1 since there are no perfect subtrees.
2. k > Number of Perfect Subtrees: If k is larger than the number of perfect subtrees, the function returns -1.
3. k = 1 and Only One Node: If the tree has only one node, it's a perfect binary tree of size 1, so if k=1, return 1.
4. Skewed Tree: In a skewed tree, the is_perfect function might take longer due to the depth of the tree, but the algorithm should still function correctly.
5. Large k: If k is very large but still within the constraint (1 <= k <= 1024), the algorithm should still work as long as the number of perfect subtrees is less than or equal to k. If it's larger, then -1 should be returned.