3319. K-th Largest Perfect Subtree Size in Binary Tree LeetCode Solution
In this guide, you will get 3319. K-th Largest Perfect Subtree Size in Binary Tree LeetCode Solution with the best time and space complexity. The solution to K-th Largest Perfect Subtree Size in Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of K-th Largest Perfect Subtree Size in Binary Tree
You are given the root of a binary tree and an integer k.
Return an integer denoting the size of the kth 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 2nd 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.
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
Complexity Analysis
Time Complexity: O(n + \texttt{sort})
Space Complexity: O(n)
3319. K-th Largest Perfect Subtree Size in Binary Tree LeetCode Solution in C++
struct T {
bool isPerfect;
int sz;
};
class Solution {
public:
int kthLargestPerfectSubtree(TreeNode* root, int k) {
vector<int> ans;
dfs(root, ans);
ranges::sort(ans, greater<>());
return ans.size() < k ? -1 : ans[k - 1];
}
private:
T dfs(TreeNode* root, vector<int>& ans) {
if (root == nullptr)
return {true, 0};
const auto l = dfs(root->left, ans);
const auto r = dfs(root->right, ans);
if (l.isPerfect && r.isPerfect && l.sz == r.sz) {
const int sz = 1 + l.sz + r.sz;
ans.push_back(sz);
return {true, sz};
}
return {false, 0};
}
}; /* code provided by PROGIEZ */
3319. K-th Largest Perfect Subtree Size in Binary Tree LeetCode Solution in Java
record T(boolean isPerfect, int sz) {}
class Solution {
public int kthLargestPerfectSubtree(TreeNode root, int k) {
List<Integer> ans = new ArrayList<>();
dfs(root, ans);
Collections.sort(ans, Collections.reverseOrder());
return ans.size() < k ? -1 : ans.get(k - 1);
}
private T dfs(TreeNode root, List<Integer> ans) {
if (root == null)
return new T(true, 0);
T l = dfs(root.left, ans);
T r = dfs(root.right, ans);
if (l.isPerfect() && r.isPerfect() && l.sz() == r.sz()) {
final int sz = 1 + l.sz() + r.sz();
ans.add(sz);
return new T(true, sz);
}
return new T(false, 0);
}
} // code provided by PROGIEZ
3319. K-th Largest Perfect Subtree Size in Binary Tree LeetCode Solution in Python
from dataclasses import dataclass
@dataclass(frozen=True)
class T:
isPerfect: bool
sz: int
class Solution:
def kthLargestPerfectSubtree(self, root: TreeNode | None, k: int) -> int:
ans = []
self._dfs(root, ans)
if len(ans) < k:
return -1
return sorted(ans, reverse=True)[k - 1]
def _dfs(self, root: TreeNode, ans: list[int]) -> T:
if not root:
return T(True, 0)
l = self._dfs(root.left, ans)
r = self._dfs(root.right, ans)
if l.isPerfect and r.isPerfect and l.sz == r.sz:
sz = 1 + l.sz + r.sz
ans.append(sz)
return T(True, sz)
return T(False, 0) # code by PROGIEZ
