Given an N-ary Tree, find out the average width of each of the nodes present in that tree.
Example:
1
/ |
2 3
/ \ / |
4 5 6 7

Note: A node can have ‘N’ number of children

Explanation: Consider the above tree, for node 1 , the average width would be the total no. of nodes under that node ie. 7 (including the target node) divided by the total number of levels under the parent node (7/3) .

The format of the answer should be: [node number : average width of that node ] that is ,for the given tree the answer is :

[ 1 : 2.5 , 2 : 1.5 , 3 : 1.5 , 4 : 1 , 5 : 1 , 6 : 1 , 7 : 1 ]

Could anyone provide an optimal approach for this problem.

1 Like

so basically the height of each node and no of nodes in the subtree of each node is required which can be pre computed

Could u provide ur algo or code for the same

here’s the code i wrote for this

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pair<int,int>
using namespace std;
vector<bool>vis(100005,0);
pp AB[100];

ll no_nodes;

pp dfs(ll node)
{
pp h={1,0};
int k=0;
vis[node]=true;
{
if(!vis[i])
{
pp tmp=dfs(i); h.first+=tmp.first; h.second=max(h.second,tmp.second);
k++;
}
}
h.second++;
AB[node]=h;
return h;
}

int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll N,M,a,b;
ll X,Y;
cin >> N;;

for(int i = 0 ; i < N-1 ; i++)
{
cin >> a >> b;
}

dfs(1);
for(int i=1;i<N+1;i++){
cout<<AB[i].first<<" "<<AB[i].second<<"\n";
float a=float(AB[i].first)/float(AB[i].second);
cout<<i<<" : "<<a<<"\n";
}

return 0;
}

here’s the example output
input:(where first input is no of nodes then subsequent edges)
7
1 2
1 3
2 4
2 5
3 6
3 7

output:
1 : 2.33333
2 : 1.5
3 : 1.5
4 : 1
5 : 1
6 : 1
7 : 1

ask if you don’t understand yet.
and yes its complexity is O(n) because of single dfs over tree

1 Like

What is the use of variable k in your dfs function?

sorry, it’s of no use

sorry it’s of no use