Problem Description

You are given the root of a binary tree and an integer k. Your task is to find the size of the k-th largest perfect binary subtree in the given tree. If there are fewer than k perfect binary subtrees in the tree, return -1.

A perfect binary tree is defined as a tree where:

• All leaf nodes are at the same level (same depth from the root)
• Every parent node has exactly two children

The problem asks you to:

1. Identify all perfect binary subtrees within the given binary tree
2. Determine the size of each perfect binary subtree (size = total number of nodes in that subtree)
3. Find the k-th largest among these sizes
4. Return this k-th largest size, or -1 if fewer than k perfect binary subtrees exist

For example, a single node is considered a perfect binary tree of size 1. A tree with a root and two leaf children forms a perfect binary tree of size 3. The algorithm needs to examine every possible subtree in the given tree to identify which ones are perfect binary trees, calculate their sizes, and then return the k-th largest size after sorting them in descending order.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we are working with a binary tree structure, where we have a root node and each node can have left and right children.

DFS

• Conclusion: The flowchart leads us directly to DFS (Depth-First Search) for tree problems.

This makes perfect sense for our problem because:

1. We need to traverse the entire tree to identify all perfect binary subtrees
2. For each node, we need to check if the subtree rooted at that node forms a perfect binary tree
3. DFS allows us to process each subtree from the bottom up, calculating the size of perfect subtrees recursively
4. At each node, we can determine if it's the root of a perfect binary subtree by checking if its left and right subtrees are perfect and have equal sizes

The DFS approach naturally fits this problem as we need to:

• Visit each node in the tree
• Compute properties (perfection and size) of subtrees before processing their parent
• Aggregate information from child nodes to parent nodes

Conclusion: The flowchart correctly identifies DFS as the optimal approach for this tree-based problem where we need to analyze properties of all subtrees.

Intuition

The key insight is that we need to identify and measure all perfect binary subtrees within the given tree. A perfect binary tree has a very specific property: all leaves are at the same depth, and every internal node has exactly two children. This means that for any perfect binary tree, the left and right subtrees must also be perfect binary trees of the exact same size.

This observation leads us to a bottom-up approach. We can start from the leaves and work our way up to the root. A leaf node by itself is a perfect binary tree of size 1. For any internal node to be the root of a perfect binary tree, both its left and right children must exist and must be roots of perfect binary trees of equal size.

Think about how we can determine if a subtree is perfect:

• If we're at a null node, we can consider it as having size 0
• If we're at a leaf node (both children are null), it's a perfect tree of size 1
• For any other node, we need to check if both left and right subtrees are perfect and have the same size

This naturally suggests a recursive DFS approach where we:

1. Recursively calculate the perfect subtree size for left and right children
2. If both children return the same positive size (or 0 for null nodes), then the current subtree is perfect with size left_size + right_size + 1
3. If the children have different sizes or one of them is not perfect (returns -1), then the current subtree is not perfect

As we traverse the tree, we can collect all the sizes of perfect subtrees we find. Once we have all sizes, finding the k-th largest is simply a matter of sorting these sizes in descending order and picking the k-th element.

The use of -1 as a sentinel value is clever here - it propagates upward to indicate that a subtree is not perfect, preventing any parent node from being incorrectly identified as perfect.

Learn more about Tree, Depth-First Search, Binary Tree and Sorting patterns.

Solution Approach

The solution implements a DFS traversal with post-order processing to identify and measure all perfect binary subtrees. Here's how the implementation works:

Core DFS Function (dfs)

The recursive dfs function calculates the size of a perfect binary subtree rooted at the current node:

1. Base Case: If the current node is None, return 0 (an empty tree has size 0)

2. Recursive Calls: Calculate the sizes of left and right subtrees:

   l, r = dfs(root.left), dfs(root.right)

3. Perfect Subtree Check: A subtree is perfect only if:

   • Both left and right subtrees are perfect (neither returns -1)
   • Both subtrees have the same size (l == r)

   If either condition fails, return -1 to indicate this subtree is not perfect:

   if l < 0 or l != r:
       return -1

4. Size Calculation: If the subtree is perfect, calculate its total size:

   cnt = l + r + 1  # left subtree + right subtree + current node

5. Store Perfect Subtree Size: Add the size to our collection:

   nums.append(cnt)

6. Return Size: Return cnt so parent nodes can use this information

Main Algorithm Flow

1. Initialize Storage: Create an empty list nums to store all perfect subtree sizes

2. Traverse Tree: Call dfs(root) to process the entire tree and populate nums

3. Check Availability: If we have fewer than k perfect subtrees, return -1:

   if len(nums) < k:
       return -1

4. Find k-th Largest: Sort the sizes in descending order and return the k-th element:

   nums.sort(reverse=True)
   return nums[k - 1]  # k-1 because of 0-based indexing

Time Complexity: O(n + m log m) where n is the number of nodes in the tree and m is the number of perfect subtrees. We visit each node once (O(n)) and sort the perfect subtree sizes (O(m log m)).

Space Complexity: O(n) for the recursion stack in the worst case (skewed tree) plus O(m) for storing perfect subtree sizes.

Example Walkthrough

Let's walk through a concrete example to understand how the algorithm works.

Consider this binary tree and let's find the 2nd largest perfect binary subtree (k=2):

        1
       / \
      2   3
     / \
    4   5

Step-by-step DFS traversal (post-order):

1. Visit node 4 (leaf):

   • Left child: dfs(None) returns 0
   • Right child: dfs(None) returns 0
   • Check: l = 0, r = 0, they're equal and non-negative
   • Size: 0 + 0 + 1 = 1
   • Add 1 to nums: nums = [1]
   • Return 1

2. Visit node 5 (leaf):

   • Left child: dfs(None) returns 0
   • Right child: dfs(None) returns 0
   • Check: l = 0, r = 0, they're equal and non-negative
   • Size: 0 + 0 + 1 = 1
   • Add 1 to nums: nums = [1, 1]
   • Return 1

3. Visit node 2:

   • Left child: dfs(4) returns 1
   • Right child: dfs(5) returns 1
   • Check: l = 1, r = 1, they're equal and non-negative
   • Size: 1 + 1 + 1 = 3
   • Add 3 to nums: nums = [1, 1, 3]
   • Return 3

4. Visit node 3 (leaf):

   • Left child: dfs(None) returns 0
   • Right child: dfs(None) returns 0
   • Check: l = 0, r = 0, they're equal and non-negative
   • Size: 0 + 0 + 1 = 1
   • Add 1 to nums: nums = [1, 1, 3, 1]
   • Return 1

5. Visit node 1 (root):

   • Left child: dfs(2) returns 3
   • Right child: dfs(3) returns 1
   • Check: l = 3, r = 1, they're NOT equal
   • This is NOT a perfect binary tree
   • Return -1

Final processing:

• All perfect subtree sizes: nums = [1, 1, 3, 1]
• Sort in descending order: [3, 1, 1, 1]
• We need the 2nd largest (k=2): nums[1] = 1
• Return 1

The algorithm correctly identifies:

• Three leaf nodes as perfect trees of size 1
• The subtree rooted at node 2 as a perfect tree of size 3
• The entire tree is NOT perfect (different subtree sizes)

The 2nd largest perfect binary subtree has size 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm consists of two main phases:

1. DFS Traversal: The dfs function visits each node in the binary tree exactly once to determine if subtrees are perfect and calculate their sizes. This takes O(n) time, where n is the total number of nodes in the tree.

2. Sorting: After collecting all perfect subtree sizes in the nums list, the algorithm sorts this list in descending order. In the worst case, if all subtrees are perfect, the nums list contains n elements (one for each node representing the perfect subtree rooted at that node). Sorting n elements takes O(n × log n) time.

Since O(n × log n) dominates O(n), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space usage comes from:

1. Recursion Stack: The DFS traversal uses the call stack, which in the worst case (skewed tree) can go as deep as n levels, requiring O(n) space.

2. nums List: This list stores the sizes of all perfect subtrees found. In the worst case, when the tree is a perfect binary tree, every subtree rooted at each node is also perfect, resulting in n entries in the list, requiring O(n) space.

3. Sorting: The sorting operation (likely using Timsort in Python) requires at most O(n) auxiliary space.

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding Perfect Binary Tree Definition

Pitfall: A common mistake is confusing a perfect binary tree with a complete or full binary tree. Developers might incorrectly validate a subtree as perfect by only checking if internal nodes have two children, without verifying that all leaves are at the same depth.

Example of Incorrect Logic:

# WRONG: Only checks if node has 0 or 2 children
def dfs(node):
    if not node:
        return 0
    if not node.left and not node.right:  # leaf node
        return 1
    if node.left and node.right:  # has both children
        left_size = dfs(node.left)
        right_size = dfs(node.right)
        return left_size + right_size + 1
    return -1  # has only one child

Solution: The correct approach ensures that left and right subtrees have equal sizes (which guarantees equal heights in a perfect tree):

if left_size < 0 or left_size != right_size:
    return -1

2. Incorrectly Handling Base Case for Empty Trees

Pitfall: Returning -1 for None nodes instead of 0, which breaks the logic for identifying leaf nodes as perfect subtrees of size 1.

Incorrect Implementation:

# WRONG: This prevents leaf nodes from being recognized as perfect subtrees
def dfs(node):
    if node is None:
        return -1  # Should be 0!
    # ... rest of logic

Solution: Return 0 for None nodes. This allows leaf nodes (with two None children) to be correctly identified as perfect subtrees since both children return 0 (equal sizes).

3. Not Collecting All Perfect Subtrees

Pitfall: Only collecting perfect subtrees when the entire check passes, missing intermediate perfect subtrees when a larger subtree isn't perfect.

Incorrect Approach:

def dfs(node):
    if not node:
        return 0
  
    left_size = dfs(node.left)
    right_size = dfs(node.right)
  
    if left_size < 0 or left_size != right_size:
        # WRONG: Not checking if children might be perfect subtrees themselves
        return -1
  
    # Only adds current subtree if it's perfect
    current_size = left_size + right_size + 1
    sizes.append(current_size)
    return current_size

Solution: The recursive nature of the correct implementation ensures all perfect subtrees are found because dfs is called on every node, and each node that forms a perfect subtree adds its size to the list before returning.

4. Off-by-One Error in k-th Element Access

Pitfall: Forgetting that list indices are 0-based when accessing the k-th largest element after sorting.

Incorrect Access:

# WRONG: Returns (k+1)-th largest element
return perfect_subtree_sizes[k]  # Should be [k-1]

Solution: Use perfect_subtree_sizes[k - 1] to correctly access the k-th largest element in a 0-indexed list.

5. Not Handling Edge Cases

Pitfall: Failing to check if there are fewer than k perfect subtrees before attempting to access the k-th element.

Problematic Code:

# WRONG: Will throw IndexError if len(sizes) < k
def kthLargestPerfectSubtree(root, k):
    sizes = []
    dfs(root)
    sizes.sort(reverse=True)
    return sizes[k - 1]  # IndexError if k > len(sizes)

Solution: Always validate that you have at least k perfect subtrees:

if len(perfect_subtree_sizes) < k:
    return -1