#3319

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

K-th Largest Perfect Subtree Size in Binary Tree

Find the size of the kth largest perfect subtree in a binary tree using tree traversal and state tracking.

tree depth first search sorting binary tree

Problem Statement

Given a binary tree root and an integer k, you need to determine the size of the kth largest perfect binary subtree. A perfect binary tree is one where all leaves are at the same depth, and each parent has exactly two children.

Return the size of the kth largest perfect subtree, or -1 if there are fewer than k perfect subtrees. You should consider binary tree traversal techniques and state management to identify all the perfect binary subtrees efficiently.

Examples

Example 1

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

Output: 3

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

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

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

Solution Approach

DFS Traversal and State Tracking

Traverse the binary tree using a depth-first search (DFS). For each subtree, check if it is a perfect binary tree by verifying that both its children are perfect. Track the size of each perfect subtree during traversal.

Sorting Subtree Sizes

Once all perfect subtree sizes are identified, store them in a list. Sort this list in non-increasing order to arrange the sizes from largest to smallest. This will allow you to access the kth largest subtree size.

Handling Edge Cases

Ensure that edge cases like having fewer than k perfect subtrees are handled. In such cases, return -1 as there is no kth largest subtree.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the traversal approach, typically O(n) for a DFS traversal. Sorting the sizes introduces an additional O(m log m) complexity, where m is the number of perfect subtrees found. Space complexity also depends on the number of perfect subtrees stored, which could be O(n) in the worst case, where n is the total number of nodes in the tree.

What Interviewers Usually Probe

Look for a solution that emphasizes tree traversal and state management.
Expect the candidate to use DFS effectively to explore each subtree.
Check if the candidate handles edge cases like fewer perfect subtrees than k.

Common Pitfalls or Variants

Common pitfalls

Failing to identify perfect subtrees correctly by not checking both children recursively.
Inefficient sorting or traversal leading to higher than necessary time complexity.
Missing the edge case where there are fewer than k perfect subtrees.

Follow-up variants

Determine the size of the largest perfect subtree without considering the kth.
Find the size of the smallest perfect subtree.
Return the number of perfect subtrees instead of their size.

FAQ

How do I find the kth largest perfect binary subtree in a binary tree?

Traverse the tree using DFS to identify all perfect binary subtrees, then sort their sizes in non-increasing order and return the kth largest size.

What is a perfect binary tree?

A perfect binary tree is one where all the leaves are at the same level and every non-leaf node has exactly two children.

What if there are fewer than k perfect subtrees?

If there are fewer than k perfect subtrees, return -1 as there is no kth largest subtree.

How can I optimize my solution for this problem?

You can optimize your solution by using DFS for efficient traversal and sorting the subtree sizes only once after collecting them.

What is the expected time complexity of this problem?

The time complexity is O(n) for DFS traversal, with an additional O(m log m) for sorting the perfect subtree sizes, where n is the number of nodes and m is the number of perfect subtrees.

terminal

Solution

Solution 1: DFS + Sorting

We define a function $\textit{dfs}$ to calculate the size of the perfect binary subtree rooted at the current node, using an array $\textit{nums}$ to record the sizes of all perfect binary subtrees. If the subtree rooted at the current node is not a perfect binary subtree, it returns $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# 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: Optional[TreeNode], k: int) -> int:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            l, r = dfs(root.left), dfs(root.right)
            if l < 0 or l != r:
                return -1
            cnt = l + r + 1
            nums.append(cnt)
            return cnt

        nums = []
        dfs(root)
        if len(nums) < k:
            return -1
        nums.sort(reverse=True)
        return nums[k - 1]

Continue Practicing

#2973 find number of coins to place in tree nodes #2641 cousins in binary tree ii #2583 kth largest sum in a binary tree