LeetCode Problem 3319

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Sorting, Binary Tree

Solution

LeetCode 3319 - K-th Largest Perfect Subtree Size in Binary Tree

Problem Understanding

We are given the root of a binary tree and an integer k. Our goal is to find the size of the k-th largest perfect binary subtree contained anywhere within the tree.

A perfect binary tree has two defining properties:

1. Every internal node has exactly two children.
2. All leaf nodes appear at the same depth.

The size of a subtree is simply the number of nodes it contains.

The input tree itself does not need to be perfect. Instead, we must examine every subtree rooted at every node and determine whether that subtree is perfect. For every perfect subtree we find, we record its size. After collecting all such sizes, we sort them in descending order and return the k-th largest value. If fewer than k perfect subtrees exist, we return -1.

The constraints are relatively small:

• Number of nodes ≤ 2000
• k ≤ 1024

With only 2000 nodes, an O(n log n) or even O(n²) solution could potentially pass. However, we can do much better by exploiting the recursive structure of binary trees.

Several edge cases are important:

• A single node is always a perfect binary tree of size 1.
• A node with exactly one child can never be the root of a perfect subtree.
• The entire tree may itself be perfect.
• There may be fewer than k perfect subtrees.
• Multiple perfect subtrees can have the same size, and each occurrence must be counted separately.

Approaches

Brute Force

A straightforward approach is to examine every node as a potential subtree root.

For each node:

1. Traverse the entire subtree.
2. Check whether all leaves are at the same depth.
3. Verify that every internal node has exactly two children.
4. If the subtree is perfect, compute its size and store it.

Since there are n possible roots and each validation may require traversing up to O(n) nodes, the overall complexity becomes O(n²).

This approach is correct because every subtree is explicitly checked, but it performs a large amount of repeated work. The same nodes are visited many times while validating overlapping subtrees.

Key Insight

A subtree is perfect if and only if:

• Its left subtree is perfect.
• Its right subtree is perfect.
• The heights of the left and right perfect subtrees are equal.

This observation suggests a postorder traversal.

When processing a node, we first determine whether its left and right subtrees are perfect. If both are perfect and their heights match, then the current subtree is also perfect.

Instead of repeatedly validating subtrees, we compute the necessary information exactly once per node and propagate it upward.

For each node, we return:

• Whether the subtree is perfect.
• Its height.
• Its size.

Whenever a perfect subtree is discovered, its size is added to a list.

After the DFS completes, we sort the collected sizes in descending order and return the k-th element if it exists.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly validates overlapping subtrees
Optimal	O(n log n)	O(n)	Single DFS collects all perfect subtree sizes

Algorithm Walkthrough

1. Create an empty list called perfect_sizes.
2. Perform a postorder DFS traversal. Postorder is important because a node can only determine whether it forms a perfect subtree after both children have already been processed.
3. For a null node, return:

• perfect = true
• height = 0
• size = 0

Treating empty subtrees as perfect simplifies the recursion. 4. Recursively process the left child and obtain:

• whether it is perfect
• its height
• its size

5. Recursively process the right child and obtain the same information.
6. Check whether the current node forms a perfect subtree:

• left subtree is perfect
• right subtree is perfect
• left height equals right height

7. If all conditions hold:

• current subtree is perfect
• height = left height + 1
• size = left size + right size + 1
• append the size to perfect_sizes
• return the computed values

8. Otherwise:

• mark the subtree as not perfect
• return any placeholder height and size values since they will not be used to form larger perfect subtrees

9. After DFS finishes, sort perfect_sizes in descending order.
10. If fewer than k sizes exist, return -1.
11. Otherwise return perfect_sizes[k - 1].

Why it works

The algorithm relies on the recursive characterization of perfect binary trees. A subtree rooted at a node is perfect exactly when both child subtrees are perfect and have identical heights. The DFS computes this information bottom-up, ensuring that every node is evaluated using already-correct information from its children. Since every perfect subtree is detected exactly once, the collected sizes are complete and correct.

Python Solution

# 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

from typing import Optional

class Solution:
    def kthLargestPerfectSubtree(
        self,
        root: Optional[TreeNode],
        k: int
    ) -> int:
        perfect_sizes = []

        def dfs(node):
            if node is None:
                return True, 0, 0

            left_perfect, left_height, left_size = dfs(node.left)
            right_perfect, right_height, right_size = dfs(node.right)

            if (
                left_perfect
                and right_perfect
                and left_height == right_height
            ):
                size = left_size + right_size + 1
                height = left_height + 1

                perfect_sizes.append(size)

                return True, height, size

            return False, 0, 0

        dfs(root)

        perfect_sizes.sort(reverse=True)

        if k > len(perfect_sizes):
            return -1

        return perfect_sizes[k - 1]

The implementation follows the postorder strategy directly.

The helper function dfs returns three values describing the subtree rooted at the current node. Empty subtrees are considered perfect with height 0 and size 0, which allows leaf nodes to naturally become perfect subtrees of size 1.

After both children are processed, the current node checks whether the perfect-tree conditions hold. If they do, the subtree size is computed and appended to perfect_sizes.

Once the traversal finishes, all perfect subtree sizes have been collected. Sorting them in descending order makes it easy to retrieve the k-th largest size.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "sort"

func kthLargestPerfectSubtree(root *TreeNode, k int) int {
    perfectSizes := []int{}

    var dfs func(*TreeNode) (bool, int, int)

    dfs = func(node *TreeNode) (bool, int, int) {
        if node == nil {
            return true, 0, 0
        }

        leftPerfect, leftHeight, leftSize := dfs(node.Left)
        rightPerfect, rightHeight, rightSize := dfs(node.Right)

        if leftPerfect && rightPerfect &&
            leftHeight == rightHeight {

            size := leftSize + rightSize + 1
            height := leftHeight + 1

            perfectSizes = append(perfectSizes, size)

            return true, height, size
        }

        return false, 0, 0
    }

    dfs(root)

    sort.Slice(perfectSizes, func(i, j int) bool {
        return perfectSizes[i] > perfectSizes[j]
    })

    if k > len(perfectSizes) {
        return -1
    }

    return perfectSizes[k-1]
}

The Go implementation mirrors the Python solution closely. The recursive helper returns a tuple represented as multiple return values. A slice stores all perfect subtree sizes, and sort.Slice is used to sort them in descending order. Since the maximum subtree size is at most 2000, integer overflow is not a concern.

Worked Examples

Example 1

Input:

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

Perfect subtrees discovered during DFS:

Root Value	Perfect Size
1	1
8	1
5	3
2	1
6	1
8	1
5	3
7	1

Collected sizes:

[1, 1, 3, 1, 1, 1, 3, 1]

After sorting:

[3, 3, 1, 1, 1, 1, 1, 1]

k = 2, so the answer is:

3

Example 2

Input:

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

DFS discovers:

Root Value	Perfect Size
4	1
5	1
2	3
6	1
7	1
3	3
1	7

Collected sizes:

[1, 1, 3, 1, 1, 3, 7]

Sorted:

[7, 3, 3, 1, 1, 1, 1]

The largest size is:

7

Example 3

Input:

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

Perfect subtrees:

Root Value	Perfect Size
4	1
3	1

Collected sizes:

[1, 1]

There are only two perfect subtrees.

Since:

k = 3

the answer is:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m log m)	DFS visits each node once, then sorts m perfect subtree sizes
Space	O(n)	Recursion stack and stored subtree sizes

Here, m is the number of perfect subtrees and m ≤ n. Since there are at most n collected sizes, the complexity can also be written as O(n log n) in the worst case. The DFS itself is linear because every node is processed exactly once.

Test Cases

# Helper constructor assumed.

# Example 1
assert Solution().kthLargestPerfectSubtree(
    build_tree([5,3,6,5,2,5,7,1,8,None,None,6,8]), 2
) == 3  # second largest perfect subtree

# Example 2
assert Solution().kthLargestPerfectSubtree(
    build_tree([1,2,3,4,5,6,7]), 1
) == 7  # entire tree is perfect

# Example 3
assert Solution().kthLargestPerfectSubtree(
    build_tree([1,2,3,None,4]), 3
) == -1  # insufficient perfect subtrees

# Single node tree
assert Solution().kthLargestPerfectSubtree(
    build_tree([1]), 1
) == 1  # leaf itself is perfect

# Single node, k too large
assert Solution().kthLargestPerfectSubtree(
    build_tree([1]), 2
) == -1  # only one perfect subtree

# Root with one child
assert Solution().kthLargestPerfectSubtree(
    build_tree([1,2]), 1
) == 1  # only leaf subtree qualifies

# Perfect tree of height 2
assert Solution().kthLargestPerfectSubtree(
    build_tree([1,2,3]), 1
) == 3  # full tree perfect

# Perfect tree of height 2, second largest
assert Solution().kthLargestPerfectSubtree(
    build_tree([1,2,3]), 2
) == 1  # leaf subtree

# Completely skewed tree
assert Solution().kthLargestPerfectSubtree(
    build_tree([1,2,None,3,None,4]), 2
) == 1  # all perfect subtrees are leaves

# Larger perfect tree
assert Solution().kthLargestPerfectSubtree(
    build_tree([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]), 1
) == 15  # largest possible perfect subtree in tree

Test Summary

Test	Why
Example 1	Validates duplicate large perfect subtrees
Example 2	Validates entire tree being perfect
Example 3	Validates insufficient subtree count
Single node	Smallest valid tree
Single node with large k	Tests -1 condition
One child only	Ensures imperfect parent handling
Perfect height-2 tree	Basic perfect-tree detection
Perfect height-2 tree, k=2	Validates ordering of subtree sizes
Skewed tree	Tests highly unbalanced structure
Large perfect tree	Confirms recursive aggregation of sizes

Edge Cases

Single Node Tree

A tree consisting of exactly one node is a perfect binary tree by definition. Both left and right subtrees are empty, and their heights are equal. The DFS correctly identifies the subtree size as 1 and records it.

Node With Only One Child

A common bug is accidentally treating a node with one missing child as perfect. The recursive rule prevents this automatically. The existing child subtree may be perfect, but the heights of the left and right sides cannot match because one side is empty and the other is not. Therefore the parent subtree is rejected.

Fewer Than k Perfect Subtrees

The problem requires returning -1 when the requested rank does not exist. After collecting and sorting all perfect subtree sizes, the implementation explicitly checks whether k exceeds the number of recorded sizes. If so, it returns -1 immediately.

Multiple Perfect Subtrees With Equal Size

Several perfect subtrees may have identical sizes. The problem asks for the k-th largest subtree, not the k-th distinct size. Therefore every perfect subtree occurrence is stored independently. If two different subtrees both have size 3, both entries remain in the list and participate separately in the ranking.

Entire Tree Is Perfect

When the root itself satisfies the perfect-tree condition, the DFS naturally computes its size after processing both children. The full tree size is appended to the collection, ensuring it competes with all smaller perfect subtrees during ranking.