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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-th Largest Perfect Subtree Size in Binary Tree

Number: 3509

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given the root of a binary tree and an integer k, find the size of the kth largest perfect binary subtree. A perfect binary subtree is one in which all leaves are on the same level and every internal node has exactly two children. If there are fewer than k perfect subtrees in the tree, return -1.

Key Insights

  • Traverse the tree using DFS (postorder traversal) so that subtrees are processed before their parent.
  • For each node, determine if it forms the root of a perfect binary subtree:
    • A leaf node is a perfect binary subtree of height 1 and size 1.
    • For an internal node, if both left and right subtrees are perfect and have the same height, then the subtree rooted at the current node is perfect.
  • Record the size of every perfect subtree encountered (including those that are parts of a larger perfect subtree).
  • After traversal, sort the collected perfect subtree sizes in descending order. The kth element in this list is the answer.
  • Be cautious in handling null children; use base-case values appropriately.

Space and Time Complexity

Time Complexity: O(n log n) in the worst-case due to sorting all perfect subtree sizes (n being the number of nodes). The DFS itself is O(n).
Space Complexity: O(n) for the recursion stack and to store the sizes of perfect subtrees.

Solution

We use a DFS (depth-first search) to traverse every node in the binary tree. At each node:

  1. If the node is a leaf, then it is by definition a perfect binary subtree with height 1 and size 1.
  2. Otherwise, recuse on both children. If both left and right subtrees are perfect and have the same height, then the current node’s subtree is also perfect. Its height is one plus the children’s height, and its size is the sum of the children’s sizes plus one.
  3. Record the size of any perfect subtree found. After the DFS traversal, sort the list of perfect subtree sizes in descending order and return the kth element if it exists, otherwise return -1.

Data structures used:

  • A list to collect perfect subtree sizes.
  • Recursion with additional tuple values (isPerfect, height, size) to keep track of subtree properties.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def kthLargestPerfectSubtree(self, root: TreeNode, k: int) -> int:
        perfect_sizes = []  # List to store the sizes of perfect subtrees

        # DFS function returns a tuple: (is_perfect, height, size)
        def dfs(node):
            if not node:
                # For null node, consider it as perfect with height 0 and size 0.
                return (True, 0, 0)
            
            # Leaf node is a perfect binary subtree.
            if not node.left and not node.right:
                perfect_sizes.append(1)  # record perfect subtree of size 1
                return (True, 1, 1)
            
            # Recurse on left and right children
            left_perfect, left_height, left_size = dfs(node.left)
            right_perfect, right_height, right_size = dfs(node.right)
            
            # Check if both subtrees are perfect and have the same height
            if left_perfect and right_perfect and left_height == right_height:
                curr_height = left_height + 1
                curr_size = left_size + right_size + 1
                # Current subtree is perfect; record its size.
                perfect_sizes.append(curr_size)
                return (True, curr_height, curr_size)
            else:
                return (False, 0, 0)
        
        dfs(root)
        
        # Sort the sizes in descending order to pick kth largest.
        perfect_sizes.sort(reverse=True)
        
        # Check if kth largest exists.
        if k > len(perfect_sizes):
            return -1
        return perfect_sizes[k - 1]

# Example Usage:
# Construct an example binary tree and call kthLargestPerfectSubtree(root, k)
← Back to All Questions