Jobs

Interviews

Discussions

K-th Largest Perfect Subtree Size in Binary Tree

Medium

Asked by:

19 views

Topics:

TreesRecursion

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.

Example 1:

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

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in non-increasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2^nd largest size is 3.

Example 2:

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

Output: 7

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

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

Output: -1

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

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

Try coding it in LeetCode

K-th Largest Perfect Subtree Size in Binary Tree

Medium

Asked by:

19 views

Topics:

TreesRecursion

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.

Example 1:

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

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in non-increasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2^nd largest size is 3.

Example 2:

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

Output: 7

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

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

Output: -1

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the node data in the binary tree, and are negative values possible?
What should I return if there are fewer than K perfect subtrees? Should I return null, -1, or throw an exception?
What defines the structure of the Binary Tree node, particularly how are children represented (e.g., left and right pointers)? Can a node have only one child?
What is the maximum number of nodes that the binary tree can have?
Can you define 'perfect subtree' more explicitly? Does it mean the subtree is a complete binary tree or a full binary tree, or something else (e.g., height-balanced)?

Brute Force Solution

Approach

The brute force approach to finding the K-th largest perfect subtree size involves checking every possible subtree within the given binary tree. For each subtree, we determine if it's a perfect binary tree and then calculate its size. Finally, we look through all the perfect subtree sizes and find the K-th largest one.

Here's how the algorithm would work step-by-step:

Consider every node in the tree as the potential root of a subtree.
For each of these nodes, check if the subtree rooted at that node is a perfect binary tree. A perfect binary tree is where all interior nodes have two children and all leaves are at the same level.
To check if a subtree is perfect, look at all its levels. The subtree is perfect if all levels are completely filled.
If a subtree is perfect, calculate the number of nodes in that subtree. This is the 'size' of the subtree.
Keep a record of the sizes of all the perfect subtrees you find.
Once you have gone through every node in the tree and checked every possible subtree, you will have a list of the sizes of all perfect subtrees.
Finally, find the K-th largest size from this list. This means sorting the list of sizes and selecting the K-th element from the end. If K is 1, you want the largest; if K is 2, you want the second largest, and so on.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def kth_largest_perfect_subtree_size(root, k_value):
    perfect_subtree_sizes = []
    def is_perfect_binary_tree(node, depth=0, level=None):
        if node is None:
            return True, level
        
        if node.left is None and node.right is None:
            if level is None:
                level = depth
            return True, level

        if node.left is None or node.right is None:
            return False, level

        is_left_perfect, left_level = is_perfect_binary_tree(node.left, depth + 1, level)
        is_right_perfect, right_level = is_perfect_binary_tree(node.right, depth + 1, level)

        return is_left_perfect and is_right_perfect and left_level == right_level, left_level

    def subtree_size(node):
        if node is None:
            return 0
        return 1 + subtree_size(node.left) + subtree_size(node.right)

    def traverse(node):
        if node is None:
            return

        # Check if the subtree rooted at the current node is perfect
        is_perfect, _ = is_perfect_binary_tree(node)
        
        if is_perfect:
            # Calculate the size of the perfect subtree
            size = subtree_size(node)
            perfect_subtree_sizes.append(size)

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

    traverse(root)

    # Remove Duplicates and Sort in Descending Order
    unique_sizes = sorted(list(set(perfect_subtree_sizes)), reverse=True)
    
    # Return Kth largest size
    if k_value <= len(unique_sizes) and k_value > 0:
        return unique_sizes[k_value - 1]
    else:
        return -1

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm considers each of the n nodes in the binary tree as a potential root of a subtree. For each of these n nodes, it checks if the subtree is perfect, which can take O(n) time in the worst case (e.g., a skewed tree where checking the height requires traversing all the way down). Therefore, since we perform an O(n) operation for each of the n nodes in the tree, the total time complexity is approximately n * n. Thus, the overall time complexity is O(n^2).

Space Complexity

O(N) – The described algorithm stores the sizes of all perfect subtrees in a list. In the worst-case scenario, every node in the tree could be the root of a perfect subtree, leading to a list containing N elements, where N is the number of nodes in the tree. Additionally, the sorting of this list, although often done in-place, can still incur O(N) space in certain implementations or due to recursive stack usage within the sort. Therefore, the auxiliary space is dominated by the list of subtree sizes, resulting in O(N) space complexity.

Optimal Solution

Approach

The most efficient way to find the k-th largest perfect subtree size involves a clever traversal of the binary tree. We want to figure out the size of each subtree and only keep track of the perfect ones, ultimately finding the k-th largest among those.

Here's how the algorithm would work step-by-step:

Start by exploring the tree from the bottom up, meaning we'll start with the smallest subtrees at the leaves.
For each subtree, check if it's a perfect binary tree. A perfect binary tree has all levels completely filled, with the same number of descendants on the left and right.
If a subtree is perfect, calculate its size (the number of nodes it contains).
Keep a running list of the sizes of all the perfect subtrees we encounter.
Once we've explored the entire tree, find the k-th largest size from our list of perfect subtree sizes. If k is 1, you want the largest. If k is 2, you want the second largest and so on. There are established techniques to quickly select the k-th largest number in a list.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def kth_largest_perfect_subtree_size(root, k_value):
    perfect_subtree_sizes = []
    
    def is_perfect_binary_tree(node):
        if not node:
            return True, 0
        
        left_perfect, left_height = is_perfect_binary_tree(node.left)
        right_perfect, right_height = is_perfect_binary_tree(node.right)
        
        #Check if both subtrees are perfect and of equal height
        if left_perfect and right_perfect and left_height == right_height:
            return True, left_height + 1
        else:
            return False, -1

    def get_subtree_size(node):
        if not node:
            return 0
        return 1 + get_subtree_size(node.left) + get_subtree_size(node.right)

    def traverse_tree(node):
        if not node:
            return

        traverse_tree(node.left)
        traverse_tree(node.right)

        is_perfect, height = is_perfect_binary_tree(node)

        # Only process perfect subtrees
        if is_perfect:
            subtree_size = get_subtree_size(node)
            perfect_subtree_sizes.append(subtree_size)

    traverse_tree(root)
    
    #Remove duplicates and sort in descending order to find kth largest
    unique_sizes = sorted(list(set(perfect_subtree_sizes)), reverse=True)

    if k_value > 0 and k_value <= len(unique_sizes):
        return unique_sizes[k_value - 1]
    else:
        return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a single depth-first traversal of the binary tree, visiting each of the n nodes once to determine if the subtree rooted at that node is perfect. The perfect subtree check at each node takes O(1) time, involving comparing heights and checking for null children. Therefore, the overall time complexity is dominated by the tree traversal, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm maintains a list of sizes of perfect subtrees encountered during the traversal. In the worst-case scenario, if every node in the binary tree is a perfect subtree of size 1 (e.g., a skewed tree), this list could store N elements, where N is the number of nodes in the binary tree. The recursive calls of the tree traversal also contribute to space complexity via the call stack, which can grow up to a depth of N in a skewed tree. Therefore, the auxiliary space used is O(N) due to the perfect subtree size list and the call stack.

Edge Cases

Case	How to Handle
Null or Empty Tree	Return an empty list if the root is null as there are no subtrees.
K is zero or negative	Return an empty list or throw an exception, as a non-positive k is not a valid input.
K is larger than the number of perfect subtrees	Return an empty list, indicating there are fewer than K perfect subtrees.
Single node tree	If the single node is a perfect binary tree (trivially true), its size is 1 and is added to the result if K is 1.
Skewed Tree (all nodes on one side)	Handle skewed trees correctly by recursively calculating subtree sizes, ensuring perfect subtrees are properly identified regardless of tree structure.
Tree with all identical node values	The algorithm determines subtree 'perfectness' based on structure, not values, so duplicate values will not impact the correctness.
Integer overflow when calculating subtree size	Use a data type that can accommodate large subtree sizes (e.g., long in Java or C++) or check for overflow during the size calculation.
Tree with very large depth, exceeding recursion limit	Consider converting the recursive solution to an iterative one with explicit stack management to avoid stack overflow errors for extremely deep trees.

Null or Empty Tree

How to Handle:

Return an empty list if the root is null as there are no subtrees.

K is zero or negative

How to Handle:

Return an empty list or throw an exception, as a non-positive k is not a valid input.

K is larger than the number of perfect subtrees

How to Handle:

Return an empty list, indicating there are fewer than K perfect subtrees.

Single node tree

How to Handle:

If the single node is a perfect binary tree (trivially true), its size is 1 and is added to the result if K is 1.

Skewed Tree (all nodes on one side)

How to Handle:

Handle skewed trees correctly by recursively calculating subtree sizes, ensuring perfect subtrees are properly identified regardless of tree structure.

Tree with all identical node values

How to Handle:

The algorithm determines subtree 'perfectness' based on structure, not values, so duplicate values will not impact the correctness.

Integer overflow when calculating subtree size

How to Handle:

Use a data type that can accommodate large subtree sizes (e.g., long in Java or C++) or check for overflow during the size calculation.

Tree with very large depth, exceeding recursion limit

How to Handle:

Consider converting the recursive solution to an iterative one with explicit stack management to avoid stack overflow errors for extremely deep trees.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the node data in the binary tree, and are negative values possible?
What should I return if there are fewer than K perfect subtrees? Should I return null, -1, or throw an exception?
What defines the structure of the Binary Tree node, particularly how are children represented (e.g., left and right pointers)? Can a node have only one child?
What is the maximum number of nodes that the binary tree can have?
Can you define 'perfect subtree' more explicitly? Does it mean the subtree is a complete binary tree or a full binary tree, or something else (e.g., height-balanced)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every node in the tree as the potential root of a subtree.
For each of these nodes, check if the subtree rooted at that node is a perfect binary tree. A perfect binary tree is where all interior nodes have two children and all leaves are at the same level.
To check if a subtree is perfect, look at all its levels. The subtree is perfect if all levels are completely filled.
If a subtree is perfect, calculate the number of nodes in that subtree. This is the 'size' of the subtree.
Keep a record of the sizes of all the perfect subtrees you find.
Once you have gone through every node in the tree and checked every possible subtree, you will have a list of the sizes of all perfect subtrees.
Finally, find the K-th largest size from this list. This means sorting the list of sizes and selecting the K-th element from the end. If K is 1, you want the largest; if K is 2, you want the second largest, and so on.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def kth_largest_perfect_subtree_size(root, k_value):
    perfect_subtree_sizes = []
    def is_perfect_binary_tree(node, depth=0, level=None):
        if node is None:
            return True, level
        
        if node.left is None and node.right is None:
            if level is None:
                level = depth
            return True, level

        if node.left is None or node.right is None:
            return False, level

        is_left_perfect, left_level = is_perfect_binary_tree(node.left, depth + 1, level)
        is_right_perfect, right_level = is_perfect_binary_tree(node.right, depth + 1, level)

        return is_left_perfect and is_right_perfect and left_level == right_level, left_level

    def subtree_size(node):
        if node is None:
            return 0
        return 1 + subtree_size(node.left) + subtree_size(node.right)

    def traverse(node):
        if node is None:
            return

        # Check if the subtree rooted at the current node is perfect
        is_perfect, _ = is_perfect_binary_tree(node)
        
        if is_perfect:
            # Calculate the size of the perfect subtree
            size = subtree_size(node)
            perfect_subtree_sizes.append(size)

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

    traverse(root)

    # Remove Duplicates and Sort in Descending Order
    unique_sizes = sorted(list(set(perfect_subtree_sizes)), reverse=True)
    
    # Return Kth largest size
    if k_value <= len(unique_sizes) and k_value > 0:
        return unique_sizes[k_value - 1]
    else:
        return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by exploring the tree from the bottom up, meaning we'll start with the smallest subtrees at the leaves.
For each subtree, check if it's a perfect binary tree. A perfect binary tree has all levels completely filled, with the same number of descendants on the left and right.
If a subtree is perfect, calculate its size (the number of nodes it contains).
Keep a running list of the sizes of all the perfect subtrees we encounter.
Once we've explored the entire tree, find the k-th largest size from our list of perfect subtree sizes. If k is 1, you want the largest. If k is 2, you want the second largest and so on. There are established techniques to quickly select the k-th largest number in a list.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def kth_largest_perfect_subtree_size(root, k_value):
    perfect_subtree_sizes = []
    
    def is_perfect_binary_tree(node):
        if not node:
            return True, 0
        
        left_perfect, left_height = is_perfect_binary_tree(node.left)
        right_perfect, right_height = is_perfect_binary_tree(node.right)
        
        #Check if both subtrees are perfect and of equal height
        if left_perfect and right_perfect and left_height == right_height:
            return True, left_height + 1
        else:
            return False, -1

    def get_subtree_size(node):
        if not node:
            return 0
        return 1 + get_subtree_size(node.left) + get_subtree_size(node.right)

    def traverse_tree(node):
        if not node:
            return

        traverse_tree(node.left)
        traverse_tree(node.right)

        is_perfect, height = is_perfect_binary_tree(node)

        # Only process perfect subtrees
        if is_perfect:
            subtree_size = get_subtree_size(node)
            perfect_subtree_sizes.append(subtree_size)

    traverse_tree(root)
    
    #Remove duplicates and sort in descending order to find kth largest
    unique_sizes = sorted(list(set(perfect_subtree_sizes)), reverse=True)

    if k_value > 0 and k_value <= len(unique_sizes):
        return unique_sizes[k_value - 1]
    else:
        return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Tree	Return an empty list if the root is null as there are no subtrees.
K is zero or negative	Return an empty list or throw an exception, as a non-positive k is not a valid input.
K is larger than the number of perfect subtrees	Return an empty list, indicating there are fewer than K perfect subtrees.
Single node tree	If the single node is a perfect binary tree (trivially true), its size is 1 and is added to the result if K is 1.
Skewed Tree (all nodes on one side)	Handle skewed trees correctly by recursively calculating subtree sizes, ensuring perfect subtrees are properly identified regardless of tree structure.
Tree with all identical node values	The algorithm determines subtree 'perfectness' based on structure, not values, so duplicate values will not impact the correctness.
Integer overflow when calculating subtree size	Use a data type that can accommodate large subtree sizes (e.g., long in Java or C++) or check for overflow during the size calculation.
Tree with very large depth, exceeding recursion limit	Consider converting the recursive solution to an iterative one with explicit stack management to avoid stack overflow errors for extremely deep trees.

Null or Empty Tree

How to Handle:

Return an empty list if the root is null as there are no subtrees.

K is zero or negative

How to Handle:

Return an empty list or throw an exception, as a non-positive k is not a valid input.

K is larger than the number of perfect subtrees

How to Handle:

Return an empty list, indicating there are fewer than K perfect subtrees.

Single node tree

How to Handle:

If the single node is a perfect binary tree (trivially true), its size is 1 and is added to the result if K is 1.

Skewed Tree (all nodes on one side)

How to Handle:

Handle skewed trees correctly by recursively calculating subtree sizes, ensuring perfect subtrees are properly identified regardless of tree structure.

Tree with all identical node values

How to Handle:

The algorithm determines subtree 'perfectness' based on structure, not values, so duplicate values will not impact the correctness.

Integer overflow when calculating subtree size

How to Handle:

Use a data type that can accommodate large subtree sizes (e.g., long in Java or C++) or check for overflow during the size calculation.

Tree with very large depth, exceeding recursion limit

How to Handle:

Consider converting the recursive solution to an iterative one with explicit stack management to avoid stack overflow errors for extremely deep trees.