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

Master LeetCode problem 3319 (K-th Largest Perfect Subtree Size in Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Medium

Tree Depth-First Search Sorting Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a postorder traversal of the binary tree. At each node, we recursively calculate the size of the subtree rooted at that node. For a subtree to be perfect, it must be a full binary tree, i.e., all internal nodes have exactly 2 children, and all leaves are at the same level. We can calculate the size of a subtree by recursively calculating the sizes of its left and right subtrees and checking if they are perfect and have the same size.

We maintain a priority queue to store the sizes of perfect subtrees in non-increasing order. Once we have collected all perfect subtree sizes, we can find the k-th largest size from the priority queue.

Space Complexity

The space complexity is O(n) for the priority queue and the recursive stack space.

Time Complexity

The time complexity of this approach is O(n^2) in the worst case, where n is the number of nodes in the binary tree.

Solution Code

class Solution {
    PriorityQueue<Integer> sizes = new PriorityQueue<>(Collections.reverseOrder());

    public int kthLargest(TreeNode root, int k) {
        postOrder(root);
        if (sizes.size() < k) return -1;
        while (k > 1) {
            sizes.poll();
            k--;
        }
        return sizes.poll();
    }

    private int postOrder(TreeNode node) {
        if (node == null) return 0;
        int left = postOrder(node.left);
        int right = postOrder(node.right);
        if (isPerfect(node, left, right)) {
            sizes.offer(left + right + 1);
        }
        return left + right + 1;
    }

    private boolean isPerfect(TreeNode node, int leftSize, int rightSize) {
        return (leftSize == 0 && rightSize == 0) || (leftSize == rightSize);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3319 (K-th Largest Perfect Subtree Size in Binary Tree)?

This page provides optimized solutions for LeetCode problem 3319 (K-th Largest Perfect Subtree Size in Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3319 (K-th Largest Perfect Subtree Size in Binary Tree)?

The time complexity for LeetCode 3319 (K-th Largest Perfect Subtree Size in Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3319 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3319 in Java, C++, or Python.

Back to LeetCode Solutions