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<ll>adj[100005];
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;
for(auto i:adj[node])
{
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;
adj[a].push_back(b);
adj[b].push_back(a);
}
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?