Depth of an N-Ary tree

Given an N-Ary tree, find depth of the tree. An N-Ary tree is a tree in which nodes can have at most N children.

Example 1:

Example 2:

N-Ary tree can be traversed just like a normal tree. We just have to consider all childs of a given node and recursively call that function on every node.

// C++ program to find the height of
// an N-ary tree
#include <bits/stdc++.h>
using namespace std;
// Structure of a node of an n-ary tree
struct Node
   char key;
   vector<Node *> child;
// Utility function to create a new tree node
Node *newNode(int key)
   Node *temp = new Node;
   temp->key = key;
   return temp;
// Function that will return the depth
// of the tree
int depthOfTree(struct Node *ptr)
    // Base case
    if (!ptr)
        return 0;
    // Check for all children and find
    // the maximum depth
    int maxdepth = 0;
    for (vector<Node*>::iterator it = ptr->child.begin();
                              it != ptr->child.end(); it++)
        maxdepth = max(maxdepth, depthOfTree(*it));
    return maxdepth + 1 ;
// Driver program
int main()
   /*   Let us create below tree
   *             A
   *         / /   
   *       B  F   D  E
   *      /     |  /|
   *     K  J    G  C H I
   *      /           
   *    N   M            L
   Node *root = newNode('A');
   cout << depthOfTree(root) << endl;
   return 0;



Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

leave a comment



load comments

Subscribe to Our Newsletter