We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K-th Largest Perfect Subtree Size in Binary Tree

Difficulty: Medium

Problem Description

You are given the root of a binary tree and an integer k. Return an integer denoting the size of the k-th 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.

Key Insights

  • A perfect binary subtree has all its nodes filled, and the number of nodes is of the form 2^h - 1, where h is the height of the tree.
  • We can perform a depth-first search (DFS) to find all perfect binary subtrees and their sizes.
  • After collecting the sizes of all perfect binary subtrees, we can sort them in non-increasing order to find the k-th largest size.
  • If there are fewer than k perfect binary subtrees, we return -1.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of nodes in the tree (due to sorting the sizes). Space Complexity: O(n), for storing the sizes of perfect binary subtrees.

Solution

We will use a depth-first search (DFS) approach to traverse the binary tree. For each node, we will check if it is the root of a perfect binary subtree. If it is, we will compute its size and store it. After traversing the entire tree, we will sort the sizes of the perfect binary subtrees in non-increasing order and return the k-th largest size.

Code Solutions

def kthLargestPerfectSubtree(root, k):
    def isPerfect(node):
        if not node:
            return 0
        left_height = isPerfect(node.left)
        right_height = isPerfect(node.right)
        if left_height == -1 or right_height == -1 or left_height != right_height:
            return -1
        return left_height + 1

    sizes = []

    def dfs(node):
        if not node:
            return
        size = isPerfect(node)
        if size != -1:
            sizes.append((1 << (size + 1)) - 1)  # size of perfect binary subtree
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    sizes.sort(reverse=True)
    return sizes[k - 1] if k <= len(sizes) else -1
← Back to All Questions