# Diameter of n-ary tree using BFS

N-ary tree refers to the rooted tree in which each node having atmost k child nodes. The diameter of n-ary tree is the longest path between two leaf nodes.
Various approaches have already been discussed to compute diameter of tree.
1. Diameter of an N-ary tree
2. Diameter of a Binary Tree in O(n)
3. Diameter of a Binary Tree
4. Diameter of a tree using DFS
This article discuss another approach for computing diameter tree of n-ary tree using bfs. Step 1: Run bfs to find the farthest node from rooted tree let say A
Step 2: Then run bfs from A to find farthest node from A let B
Step 3: Distance between node A and B is the diameter of given tree

 `// C++ Program to find Diameter of n-ary tree ` `#include ` `using` `namespace` `std; ` ` `  `// Here 10000 is maximum number of nodes in ` `// given tree. ` `int` `diameter; ` ` `  `// The Function to do bfs traversal. ` `// It uses iterative approach to do bfs ` `// bfsUtil() ` `int` `bfs(``int` `init, vector<``int``> arr[], ``int` `n) ` `{ ` `    ``// Initializing queue ` `    ``queue<``int``> q; ` `    ``q.push(init); ` ` `  `    ``int` `visited[n + 1]; ` `    ``for` `(``int` `i = 0; i <= n; i++) { ` `        ``visited[i] = 0; ` `        ``diameter[i] = 0; ` `    ``} ` ` `  `    ``// Pushing each node in queue ` `    ``q.push(init); ` ` `  `    ``// Mark the traversed node visited ` `    ``visited[init] = 1; ` `    ``while` `(!q.empty()) { ` `        ``int` `u = q.front(); ` `        ``q.pop(); ` `        ``for` `(``int` `i = 0; i < arr[u].size(); i++) { ` `            ``if` `(visited[arr[u][i]] == 0) { ` `                ``visited[arr[u][i]] = 1; ` ` `  `                ``// Considering weight of edges equal to 1 ` `                ``diameter[arr[u][i]] += diameter[u] + 1; ` `                ``q.push(arr[u][i]); ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// return index of max value in diameter ` `    ``return` `int``(max_element(diameter + 1, ` `                           ``diameter + n + 1) ` `               ``- diameter); ` `} ` ` `  `int` `findDiameter(vector<``int``> arr[], ``int` `n) ` `{ ` `    ``int` `init = bfs(1, arr, n); ` `    ``int` `val = bfs(init, arr, n); ` `    ``return` `diameter[val]; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``// Input number of nodes ` `    ``int` `n = 6; ` ` `  `    ``vector<``int``> arr[n + 1]; ` ` `  `    ``// Input nodes in adjacency list ` `    ``arr.push_back(2); ` `    ``arr.push_back(3); ` `    ``arr.push_back(6); ` `    ``arr.push_back(4); ` `    ``arr.push_back(1); ` `    ``arr.push_back(5); ` `    ``arr.push_back(1); ` `    ``arr.push_back(2); ` `    ``arr.push_back(2); ` `    ``arr.push_back(1); ` ` `  `    ``printf``(````"Diameter of n-ary tree is %d "````, ` `           ``findDiameter(arr, n)); ` ` `  `    ``return` `0; ` `} `

Output:

```Diameter of n-ary tree is 3
```