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?
