Google Interview Question

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?

sorry, it’s of no use
:sweat_smile: :sweat_smile:

sorry it’s of no use :sweat_smile: :sweat_smile: