Facebook Pixel

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

MediumTreeDepth-First SearchBinary TreeSorting
Leetcode Link

Problem Description

You are given the root of a binary tree and an integer k. The task is to return an integer that represents the size of the k^th largest perfect binary subtree, or -1 if it doesn't exist.

A perfect binary tree is defined as a tree where all leaves are located on the same level, and every parent node has exactly two children.

Intuition

The solution involves performing a Depth-First Search (DFS) to explore the tree and determine the size of any perfect binary subtrees. The approach is to recursively calculate the size of the perfect binary subtrees for each node's left and right children.

Here's a breakdown of the process:

  1. Use a helper function dfs that operates recursively:

    • If a node is null, it indicates the absence of a subtree, returning a size of 0.
    • Compute the subtree sizes for the left (l) and right (r) children.

  2. For a subtree to be perfect, the left and right subtree sizes must be equal. If not, it cannot form a perfect binary tree, and we return -1.

  3. If both subtrees are perfect (i.e., l equals r), compute the size of the current subtree as l + r + 1, and record this size.

  4. The recorded sizes are stored in a list. Once the DFS is complete, this list contains the sizes of all perfect binary subtrees present in the tree.

  5. To find the k^th largest perfect binary subtree:

    • Sort the list of subtree sizes in descending order.
    • If the list has fewer than k elements, return -1, as the k^th largest perfect binary subtree does not exist.
    • Otherwise, return the k^th element from the sorted list.

This approach efficiently combines DFS with sorting to determine the required subtree size, leveraging the properties of perfect binary trees.

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

Solution Approach

The solution employs a Depth-First Search (DFS) strategy combined with sorting to determine the k-th largest perfect binary subtree. Here's a step-by-step explanation of the implementation:

  1. Define the dfs Function:

    • Start with a recursive function dfs that calculates the size of a perfect binary subtree rooted at the current node.
    • If the node is None, return 0, indicating no subtree exists there.

  2. Calculate Sizes of Subtrees:

    • Recursively apply dfs to the left and right children, obtaining their sizes as l and r.
    • If either subtree is not perfect (either size is negative) or if their sizes do not match (l != r), this node cannot be the root of a perfect binary subtree, so return -1.

  3. Compute Subtree Size:

    • If both subtrees are perfect and of equal size, compute the current subtree size as cnt = l + r + 1.
    • Store cnt in a list called nums containing sizes of all perfect binary subtrees encountered.

  4. Collect and Sort Sizes:

    • After traversing the entire tree, the nums list contains sizes of all perfect binary subtrees found.
    • If the length of nums is less than k, there aren't enough subtrees to find the k-th largest, so return -1.

  5. Return k-th Largest Size:

    • Sort nums in descending order and return the k-th element (nums[k - 1]), which corresponds to the k-th largest perfect binary subtree.

This approach is embodied in the function kthLargestPerfectSubtree within the provided code:

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]

This solution effectively combines DFS for tree exploration with sorting, making it efficient in locating the desired perfect binary subtree.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small binary tree to demonstrate the solution approach:

      1
     / \
    2   3
   /|   |\
  4 5   6 7

In this binary tree, every level is fully filled, making it a perfect binary tree. We need to find the 1st largest perfect binary subtree's size.

Steps to Solve:

  1. Define the dfs Function:

    • Start the recursive dfs function at the root node (value 1).

  2. Calculate Sizes of Subtrees:

    • Traverse to the left child (value 2), and further to its children (values 4 and 5), both of which are leaves with no children.
    • Since 4 and 5 each have 0 as the size of non-existent children, they both become roots of perfect subtrees with size 1 (0 + 0 + 1).

  3. Return to Node 2:

    • Node 2 has left and right subtrees of the same size (1 each), which makes this subtree perfect.
    • Calculate subtree size rooted at 2 as 1 (size of left child) + 1 (size of right child) + 1 = 3.
    • Append 3 to nums.

  4. Calculate Right Subtree from Node 3:

    • Similarly, traverse to node 3 and its children (6 and 7).
    • Nodes 6 and 7 also form perfect subtrees with size 1 each.
    • Node 3 is the root of a perfect binary subtree with size 3 (1 + 1 + 1).
    • Append another 3 to nums.

  5. Calculate Total Tree Size from Root Node 1:

    • Both left (2) and right (3) subtrees are perfect and equal, making the entire tree a perfect subtree.
    • Subtree size rooted at 1 is 3 + 3 + 1 = 7.
    • Append 7 to nums.

  6. Collect and Sort Sizes:

    • nums list after DFS: [3, 3, 7].
    • Sort nums in descending order: [7, 3, 3].

  7. Return the k-th Largest Perfect Subtree Size:

    • With k = 1, return the first element: 7.

Thus, the size of the 1st largest perfect binary subtree is 7.

Solution Implementation

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7
8class Solution:
9    def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:
10        def dfs(node: Optional[TreeNode]) -> int:
11            # Base case: if the node is null, it contributes 0 to the size of the subtree
12            if node is None:
13                return 0
14
15            # Recursively calculate the size of left and right subtrees
16            left_size = dfs(node.left)
17            right_size = dfs(node.right)
18
19            # If left subtree size is invalid, or sizes do not match, mark this subtree as invalid
20            if left_size < 0 or left_size != right_size:
21                return -1
22
23            # Calculate the size of this subtree
24            subtree_size = left_size + right_size + 1
25
26            # Add this subtree size to the list
27            subtree_sizes.append(subtree_size)
28
29            return subtree_size
30
31        # List to store sizes of all perfect subtrees
32        subtree_sizes = []
33
34        # Perform DFS to find all perfect subtrees
35        dfs(root)
36
37        # If there are fewer than k perfect subtrees, return -1
38        if len(subtree_sizes) < k:
39            return -1
40
41        # Sort the sizes of the perfect subtrees in descending order
42        subtree_sizes.sort(reverse=True)
43
44        # Return the k-th largest size
45        return subtree_sizes[k - 1]
46
1import java.util.ArrayList;
2import java.util.Comparator;
3import java.util.List;
4
5// Definition for a binary tree node
6public class TreeNode {
7    int val;
8    TreeNode left;
9    TreeNode right;
10  
11    TreeNode() {}  // default constructor
12  
13    TreeNode(int val) { 
14        this.val = val;
15    }
16  
17    TreeNode(int val, TreeNode left, TreeNode right) {
18        this.val = val;
19        this.left = left;
20        this.right = right;
21    }
22}
23
24class Solution {
25    // List to store sizes of perfect subtrees
26    private List<Integer> subtreeSizes = new ArrayList<>();
27
28    // Method to find the kth largest perfect subtree size
29    public int kthLargestPerfectSubtree(TreeNode root, int k) {
30        calculateSubtreeSizes(root);
31      
32        // If there are fewer than k subtrees, return -1 indicating an error or non-existence
33        if (subtreeSizes.size() < k) {
34            return -1;
35        }
36      
37        // Sort the subtree sizes in descending order
38        subtreeSizes.sort(Comparator.reverseOrder());
39      
40        // Return the kth largest size
41        return subtreeSizes.get(k - 1);
42    }
43
44    // Helper method to calculate the size of each perfect subtree
45    private int calculateSubtreeSizes(TreeNode root) {
46        if (root == null) {
47            return 0; // Base case: null tree has size zero
48        }
49      
50        // Recursive case: calculate size of left and right subtrees
51        int leftSize = calculateSubtreeSizes(root.left);
52        int rightSize = calculateSubtreeSizes(root.right);
53      
54        // If not perfect subtree, return -1
55        if (leftSize < 0 || leftSize != rightSize) {
56            return -1;
57        }
58      
59        // Calculate current subtree size
60        int currentSize = leftSize + rightSize + 1;
61      
62        // Add current subtree size to list
63        subtreeSizes.add(currentSize);
64      
65        return currentSize; // Return current subtree size
66    }
67}
68
1#include <vector>
2#include <algorithm>
3#include <functional>
4using namespace std;
5
6// Definition for a binary tree node.
7struct TreeNode {
8    int val;                // Value of the node
9    TreeNode *left;         // Pointer to the left child
10    TreeNode *right;        // Pointer to the right child
11
12    // Default constructor
13    TreeNode() : val(0), left(nullptr), right(nullptr) {}
14
15    // Constructor with value
16    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
17
18    // Constructor with value, and left and right children
19    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
20};
21
22class Solution {
23public:
24    // Function to find the k-th largest perfect subtree in the binary tree
25    int kthLargestPerfectSubtree(TreeNode* root, int k) {
26        vector<int> subtreeSizes;  // Vector to store sizes of perfect subtrees
27
28        // Lambda function for depth-first search
29        function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
30            if (!node) {
31                return 0;  // Base case: if node is null, subtree size is 0
32            }
33
34            // Calculate the size of the left and right subtrees
35            int leftSize = dfs(node->left);
36            int rightSize = dfs(node->right);
37
38            // If left and right subtrees are not of the same size or if any is invalid
39            if (leftSize < 0 || leftSize != rightSize) {
40                return -1;  // Return -1 to indicate this is not a perfect subtree
41            }
42
43            int currentSubtreeSize = leftSize + rightSize + 1;  // Current subtree size
44            subtreeSizes.push_back(currentSubtreeSize);  // Add the size to the collection
45            return currentSubtreeSize;  // Return current subtree size
46        };
47
48        // Start DFS from the root of the tree
49        dfs(root);
50
51        // If there are fewer than k perfect subtrees, return -1 because we can't find k-th
52        if (subtreeSizes.size() < k) {
53            return -1;
54        }
55
56        // Sort the subtree sizes in descending order
57        sort(subtreeSizes.begin(), subtreeSizes.end(), greater<int>());
58
59        // Return the k-th largest subtree size
60        return subtreeSizes[k - 1];
61    }
62};
63
1/**
2 * Definition for a binary tree node.
3 * A node in a binary tree with an integer value, left child, and right child.
4 */
5interface TreeNode {
6    val: number;
7    left: TreeNode | null;
8    right: TreeNode | null;
9    constructor: (val?: number, left?: TreeNode | null, right?: TreeNode | null) => void;
10}
11
12/**
13 * This function finds the k-th largest perfect subtree in a binary tree.
14 * A perfect subtree is a subtree where all levels are fully filled.
15 * 
16 * @param root - The root of the binary tree.
17 * @param k - The k-th largest perfect subtree size to find.
18 * @returns The size of the k-th largest perfect subtree if it exists, -1 otherwise.
19 */
20function kthLargestPerfectSubtree(root: TreeNode | null, k: number): number {
21    // Array to store sizes of perfect subtrees
22    const subtreeSizes: number[] = [];
23
24    /**
25     * Helper function that performs a depth-first search on the tree.
26     * 
27     * @param node - Current node being processed.
28     * @returns The size of the perfect subtree if it exists, -1 otherwise.
29     */
30    const dfs = (node: TreeNode | null): number => {
31        if (!node) {
32            // Base case: return 0 for null nodes
33            return 0;
34        }
35
36        // Recursively calculate left and right subtree sizes
37        const leftSize = dfs(node.left);
38        const rightSize = dfs(node.right);
39
40        // If left size is negative or the sizes of left and right subtrees don't match
41        if (leftSize < 0 || leftSize !== rightSize) {
42            return -1;
43        }
44
45        // Calculate the size of the current perfect subtree
46        const currentSubtreeSize = leftSize + rightSize + 1;
47        subtreeSizes.push(currentSubtreeSize);
48
49        return currentSubtreeSize;
50    };
51
52    // Initiate depth-first search from root
53    dfs(root);
54
55    // Check if there are enough perfect subtree sizes to get the k-th largest
56    if (subtreeSizes.length < k) {
57        return -1;
58    }
59
60    // Sort the sizes in descending order and return the k-th largest
61    return subtreeSizes.sort((a, b) => b - a)[k - 1];
62}
63

Time and Space Complexity

The time complexity of the code is O(n × log n), where n is the number of nodes in the binary tree. This complexity arises as follows:

  1. The dfs function performs a traversal of the entire tree, which takes O(n) time.
  2. After the traversal, the list nums containing the sizes of perfect binary subtrees is sorted. Sorting this list has a time complexity of O(n log n).

Combining these two, the overall time complexity is O(n + n log n), which simplifies to O(n log n).

The space complexity is O(n), arising from:

  1. The recursion stack, which can be up to O(h), where h is the height of the tree. In the worst case (a skewed tree), h can be n, making the space for the stack O(n).
  2. The list nums that stores subtree sizes, which can contain up to n elements, also contributing O(n).

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

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More