Problem: Given edges for a tree find the diameter of the tree or the longest path in the tree.
Sample Input:
4
5 1
1 3
1 2
2 4
Representation of tree: Tree can be represented in multiple ways,
1. If we simplify the problem and say it is a binary tree we can represent it as array where a[i]-> left is a[2*i] and a[i]->right is a[2*i+1].
2. One other way to represent it is by using parent array: parrent[i] = j if there is an edge j->i but the tree needs to be directed in this case
3. We can have a struct/class Node which has pointers to left and right
Node {
int val,
Node* left,
Node* right
}
To calculate the diameter of a tree we have to pick a root and do dfs/bfs to find the left node with maximum distance and find the farthest node from it.
