Count elements in all subtrees

Easy

0/40

Average time to solve is 10m

14 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

7 2 1 3 1 1 1

Explanation for sample input 1:

The above tree looks like -

The subtrees rooted at 5, 2, 6, 4 have 1 node each.
The subtree rooted at 1 has 2 nodes.
The subtree rooted at 3 has 3 nodes.
The subtree rooted at 0 has 7 nodes.
Hence, the output is {1, 1, 1, 1, 2, 3, 7}.

Sample Input 2:

Sample Output 2:

1 1 3

Hint 1

DFS

Approaches (1)

Approach 1

DFS

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.

Time Complexity

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

As a single DFS takes O(N).

Space Complexity

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

As we are creating an auxiliary array to store the answers.

(100% EXP penalty)

Count elements in all subtrees

Console