Count Special Nodes In Generic Tree

Posted: 1 Aug, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You have been given a Generic Tree of Integers. The task is to count the number of 'Special Nodes'.

A Node is a Special Node if there is a path from the root to that Node with all distinct elements.

Input format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and only line of each test case or query contains Elements in level order form separated by space (as per done in class). Order is - 
Root_data, n (No_Of_Child_Of_Root), n children, and so on for every element

Elements are in the level order form and on a level from left to right.

For example, the input for the tree depicted in the below image would be :

alt text

1
2
2 3
1
4
2
5 6
1
7
0
0
0

Explanation :

Level 1 :
The root node of the tree has value 1 hence the first value. Now, on the second line, we have 2 which means root has 2 children. The values of the two children are 2 and 3 which is given on the third line.

Level 2 :
Now, in the level order traversal, we visit the data node 2 and see the number of children it has, which is given on the fourth line followed by the value(s) of its child/children. Here, data node 2 has only 1 child and hence the value mentioned on the fifth line is 4.

Next node in the level order traversal is the data node 3. It has 2 children as given on the 6th line. After that, on the 7th line, we have the values of its children which are 5 and 6.

Level 3 :
The first node on level three is 4 and it has 1 child as mentioned on the eighth line. On the ninth line, we have the value of the child as 7.
The second node is 5 which has 0 or no children and has been mentioned on the tenth line.
The third node is 6 which has 0 or no children and has been mentioned on the eleventh line.

Level 4 :
There is only 1 node at level 4 which is 7 and has 0 children or no children as mentioned on the twelfth line. 

As every node has 0 children now the input ends.
Note :
The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 2 3 1 4 2 5 6 1 7 0 0 0
Output format :
For each test case/query, print the number of Special Nodes present in the given Generic Tree.

Output for every test case will be printed in a separate line.
Note:
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10^2
1 <= N <= 3000
0 <= Value of Tree Node <= 10^9

Time Limit: 1sec

Where 'T' is the number of Test Cases and 'N' is the number of nodes in Generic Tree.
Approach 1

We will do a recursive Depth First Search keeping a vector/list to check for the distinct element.

  1. We start the recursive DFS from the “root” node with an empty vector/list.
  2. Let’s say we are at some node “x” of the Tree with a vector/list containing all the elements from root to that node.
  3. If the value of the node “x” is present in the vector/list then it means our distinct element condition is violating so return 0.
  4. Else insert the value of node “x” in vector/list and initialize the count of special nodes with 1.
  5. Now recurse for children of node “x” with updated vector/list to count the special nodes in subtree of “x”.
  6. Now delete the value of node “x” from vector/list to make sure that all other child elements have been removed from the vector/list when we move to the next child
  7. Return the total count of special nodes
Try Problem