Good Subtrees Problem Of The Day GFG

Problem Link:

https://practice.geeksforgeeks.org/problems/df12afc57250e7f6fc101aa9c272343184fe9859/1

Solution :

class Solution

{

    // static LinkedHashSet<Integer> set1=new LinkedHashSet<Integer>();

    // static LinkedHashSet<Integer> set2=new LinkedHashSet<Integer>();

   

    public static LinkedHashSet<Integer> fun(Node root, int k,int[] count){

        if(root==null){

            return new LinkedHashSet<Integer>();

        }

        else{

            LinkedHashSet<Integer> set1=fun(root.left,k,count);

            LinkedHashSet<Integer> set2=fun(root.right,k,count);

            set1.addAll(set2);

            set1.add(root.data);

           

            if(set1.size()<=k){

                // System.out.println(set1);

                count[0]++;

            }

            return set1;

        }

    }

    

    public static int goodSubtrees(Node root,int k)

    {

        if(root==null){

            return 0;

        }

        else{

            int count[]={0};

            

            fun(root,k,count);

            return count[0];

        }

    }

}

Approach Used:

Here we will use the approach :

1. seeing left unique nodes

2. seeing the right unique nodes

3. combining 1 and 2 results with the root node and then seeing if the total distinct nodes count is <=k then res++ 

Since we need to have data for unique nodes we will use a data structure that will store the unique nodes only.

And that data structure is set.

The Set will maintain the unique node's record and set. size() will be the count of unique nodes.

Now, we understand that we need to use a set but how we will code it:

We divided the problem into breakpoints ie the different conditions which we will face while solving the problem.

1. The root is null

2. Root left child and right child are null

3. Else leftover nodes. Having 2 children or 1 child.

Now understand the problem as we need the count of distinct nodes on the left, and the count of distinct nodes on the right.

So for having those counts of unique nodes can we have to use an integer set in the left and the same in the right.

So now we understand everything, we can code.

1. If the root is null ==> then the question will return a null set.

2. If both children are empty then it means it is a leaf node.==>

if k>=1

    then in every case, these leaf nodes will be counted in the answer. Since leaf nodes in them are the subtree with distinct nodes counter<=k 

else

    then they won't be counted in the answer.

3. Else conditions 

if we think over them then for all the subtrees we require

    1. counter from left ie set1

    2. counter form right ie set2

    so left1=fun(root.left);

    and right1=fun(root.right);

    and also taking 3. root node into account 

    So,

    1+2+3<=k

    set1+set2+root node<=k

    so for adding one set into another, we will use the function set1.addAll(set2) 

    and for adding root data into the set simply we will use set. add(root. data)

Since we have deduced all the conditions and written pseudocode then now we can easily write down the code.

Here we will make an array of one integer size so that we regularly update it as it will store our result value.

If we look clearly then condition 2 is a proper subset of condition 3 as when both left and right children are null then we will have null sets and adding root data into it means a set with only one data value.

So we are done with the approach, pseudocode as well as with the code.

Time Complexity: O(n*k)[Recursion on all the nodes][GFG time:0.99]

Space Complexity: O(n+n*k)[Space for storing the data in the set and recursive call stack for n calls.][GFG]

Total Test Cases: 1025

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"