PREP66 Editorial

editorial
1

Problem Explanation

You are given a tree and you have to output the height of the given tree.

Approach

We use DFS to traverse the tree and return the height of each node. At each function call, for every child we take the height of that node and save the maximum height among all the children after adding 1 for the current node. After visiting each node we return the maximum height

Code

#include <bits/stdc++.h>
using namespace std;

int heightOfTree(int n, vector<vector<int>>& conn, vector<bool> vis){
    vis[n] = true;
    int height = 1;
    for(auto i: conn[n]){
        if(!vis[i])
        {
            height = max(height, 1+heightOfTree(i, conn, vis));
        }
    }
    return height;
}

int main() {
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<vector<int>> conn(n+1);
        vector<bool> vis(n+1, false);
        for(int i=0; i<n-1; i++){
            int a, b;
            cin>>a>>b;
            conn[a].push_back(b);
            conn[b].push_back(a);
        }
        cout<<heightOfTree(1, conn, vis)<<endl;
    }
	return 0;
}