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 <bits/stdc++.h>
using namespace std;
// Here 10000 is maximum number of nodes in
// given tree.
int diameter[10001];
// 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;
    int visited[n + 1];
    for (int i = 0; i <= n; i++) {
        visited[i] = 0;
        diameter[i] = 0;
    // Pushing each node in queue
    // Mark the traversed node visited
    visited[init] = 1;
    while (!q.empty()) {
        int u = q.front();
        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;
    // 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
    printf("Diameter of n-ary tree is %d ",
           findDiameter(arr, n));
    return 0;


Diameter of n-ary tree is 3

This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment



load comments

Subscribe to Our Newsletter