Count the nodes.

Moderate
0/80
3 upvotes
Asked in companies
Morgan StanleyAdobeAmazon

Problem statement

Ninja found an old book that has a given tree of numbers. Ninja is interested to find the number of members of that tree that has more children than its parent.

There are ‘N’ nodes in the tree and each node is indexed with a number between 0 to ‘N’-1. The tree is given in a form of an ‘EDGES’ array. Each element of ‘EDGES’ has two values, denoting an edge between that two nodes. The root of the tree is Node 0. Your task is to find the number of nodes having more children than their parent’s node.

For Example 
For the given ‘EDGES’ = [ [0,1],[1,2],[1,3],[1,4] ] and ‘N’ = 5.The number of nodes satisfying the condition is 1. Only Node 1 satisfies the given condition.

alt-text

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’ denoting the number of nodes in the tree.

The next N-1 lines of each test case have two integers denoting an edge between them.
Output Format: 
For each test case, print an integer corresponding to the number of nodes fulfilling the given condition.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 5000.
0 <= Node Index in EDGES <= N-1.

Time limit: 1 sec
Sample Input 1:
2
5
0 1
1 2
1 3
1 4
3
0 1
0 2
Sample Output 1:
1
0
Explanation of sample input 1:
For the first test case,
The number of nodes satisfying the condition is 1. 
Only Node 1 satisfies the given condition as no of children of Node 1 is 3 and no of children of its parent (Node 0) is 1. Hence the answer is 1.

alt-text

For the second test case:
There are no nodes that fulfill the given condition. 
Hence the answer is 0.

alttext

Sample Input 2:
2
6
0 1
1 2
1 3
1 4
2 5
6
0 1
0 2
1 3
1 4
1 5
Sample Output 2:
1
1
Hint

Try to store the children’s count of each node.

Approaches (2)
Using Parent array.

In this approach, we will create a ‘PARENT’ array to store the parent of each index and a ‘COUNT’ array to store the number of children of each node.

For each edge in ‘EDGES’, we will update the ‘COUNT’ and ‘PARENT’ array. After that, we will iterate over all nodes and check if ‘COUNT’[i] > COUNT[PARENT[i]] and increment our final answer accordingly.

 

Algorithm:

  • Declare an array ‘PARENT’ that will store the parents of each node.
  • Declare an array ‘COUNT’ to store the number of children of each node.
  • For each ‘EDGE’ in EDGES.do the following:
    • Set ‘PARENT’[ EDGE[1] ] = EDGE[0].
    • Set COUNT[EDGE [0] ] = COUNT[EDGE [0] ] + 1.
  • Declare a variable ANS to store the number of nodes fulfilling the given condition.
  • Set ‘ANS’ as 0.
  • For each IDX in the range from 1 to ‘N’-1, do the following:
    • If the ‘COUNT[‘IDX’] is greater than COUNT[PARENT [‘IDX’ ]]:
      • Set ‘ANS’ as ‘ANS’ + 1.
  • Return ‘ANS’.
Time Complexity

O(N), where ‘N’ is the number of nodes in the given tree.

 

In this approach, we are iterating over all edges to fill the ‘PARENTS’ and ‘COUNT’ arrays and there are only N-1 edges and so iterated over all the nodes to calculate the answer. Hence the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the given tree.

 

In this approach, we are using ‘PARENTS’ and ‘COUNT’ arrays which are of size N. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Count the nodes.
Full screen
Console