Last Updated: 10 Sep, 2021
Count the nodes.
Moderate
Asked in companies
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.
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
Approaches
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.
- If the ‘COUNT[‘IDX’] is greater than COUNT[PARENT [‘IDX’ ]]:
- Return ‘ANS’.
In this approach, First, we will represent the tree into an adjacency list manner. TREE[i] will consist of all the indices of children of Node ‘i’. We will define a function DFS(‘CUR’, ’TREE’) that will recursively iterate over all the nodes of the tree and if the number of children of ‘CUR’ is greater than the number of children of its parent. We will increment our answer.
Algorithm:
- Defining function DFS(‘CUR’, ’TREE’):
- Set ‘ANS’ as 0.
- For each ‘IDX’ in TREE[‘CUR’], do the following:
- If the length of TREE[‘IDX’] is greater than the length of TREE[‘CUR’], means the given condition is satisfied for Node ‘IDX’.
- Set ‘ANS’ as ‘ANS’ +1.
- Recursive call for the children of current Node.
- Set ‘ANS’ as ‘ANS’ + DFS(‘IDX’, ‘CUR’).
- If the length of TREE[‘IDX’] is greater than the length of TREE[‘CUR’], means the given condition is satisfied for Node ‘IDX’.
- Return ‘ANS’.
- Declare a dynamic 2-D array ‘TREE’ to store the given tree in an adjacency list manner.
- For each ‘EDGE’ in ‘EDGES’, do the following:
- Insert EDGE[1] into TREE[ ‘EDGE’[0]].
- Set ‘ANS’ as DFS(0,’TREE’).
- Return ‘ANS’.