Last Updated: 6 Jan, 2021
Count elements in all subtrees
Easy
Asked in companies
You are given an arbitrary tree consisting of 'N' nodes numbered from 0 to 'N' - 1. You need to find the total number of elements in all the subtrees of the given tree. In other words, given a generic tree, find the count of elements in the subtrees rooted at each node.
A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree. For better understanding, refer to the image below:-
Note:
1. The tree will always be rooted at 0.
2. You can return the count of nodes in any order.
3. The root of any subtree is also counted in the subtree thus the count of nodes in a subtree rooted at a leaf node is
4. You can return the numbers in any order.
Input Format:
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case consists of a single integer 'N', representing the number of nodes in the given tree.
The next 'N' - 1 lines of each test case contain two space-separated integers 'U' and 'V', denoting an edge between the node 'U' and the node 'V'.
Output Format:
For each test case, print the number of nodes in all subtrees of the given tree, in any order.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N, E <= 10^4
0 <= U,V < N
Time Limit: 1sec
Approaches
An easy way to solve this problem will be to run a modified DFS over the given tree.
- Create the output array, “arr” of size ‘N’, where ‘N’ is the number of nodes in the tree.
- Call the DFS function with source as 0, parent of source as -1(root has no parent) and the given adjacency list.
- In the DFS function, initialize the count of nodes in the subtree rooted at src with 1.
- Then, iterate through all the immediate children(‘it’) of src and recursively call the call DFS function with the current neighbour as the source and original src as a parent.
- Finally, update the count of nodes in the current subtree by adding the number of nodes in neighbour’s subtree to it.