C++ program to find the depth of a N-ary Tree

In this blog, today we’ll try to find the maximum depth of an array given an N-ary Tree in C++.

WHAT IS AN N-ARY TREE?

An N-ary Tree is a tree in which every vertex has no more than N children.
Note: Binary Tree is an example of a 2-ary Tree.

 

Ex:

Given image is an example of a 5-Ary tree as at each vertex there are no more than 5 children present.

SOLUTION

To solve this problem, we can travel through each child node of a vertex recursively and call the function, that is used to calculate depth, on each of these child vertices and keep a track of the max depth for the same.

#include <iostream>
#include<vector>
using namespace std;

//Creating a node structure
struct node {
  int data;
  static int N;
  vector<node*> AllChildren;
};


//A function to create new nodes 
node* CreateNode(int data)
{
  node* temp = new node();
  temp->data = data;
  return temp;
}

//A function to add a child to a parent
void createChild(node* parent,node* child)
{
  parent->AllChildren.push_back(child);	
}

//Funciotn that will give the depth of the tree
int depthofTree(node* root)
{
  //i.e if root = NULL
  if(!root)
    return 0;
  
  //initiall maxDepth = 0	
  int maxDepth = 0;
  for(int i=0;i<root->AllChildren.size();i++)
  {
    //Only change the maxDepth if the depth found is greater than the
    //previously found maxDepth
    maxDepth = max(maxDepth,depthofTree(root->AllChildren[i]));
  }

  return maxDepth + 1;
}

int main() {
  /*
  Here we are going to create the 5-Ary tree which was given in the example
                  1
            
              /	/	|	\	\
            
               2   3    4    5    6
              
              /  |  \         / \    |
            
            7  8   9       10  11  12
            
              / \
            
            13	 14
  */
  
  node* root = CreateNode(1);
  root->N = 5;
  createChild(root,CreateNode(2));
  createChild(root,CreateNode(3));
  createChild(root,CreateNode(4));
  createChild(root,CreateNode(5));
  createChild(root,CreateNode(6));
  
  createChild(root->AllChildren[0],CreateNode(7));
  createChild(root->AllChildren[0],CreateNode(8));
  createChild(root->AllChildren[0],CreateNode(9));
  
  createChild(root->AllChildren[3],CreateNode(10));
  createChild(root->AllChildren[3],CreateNode(11));

  createChild(root->AllChildren[4],CreateNode(12));
  
  createChild(root->AllChildren[0]->AllChildren[1],CreateNode(13));
  createChild(root->AllChildren[0]->AllChildren[1],CreateNode(14));
  
  cout<<depthofTree(root);
  return 0;
}

OUTPUT:
4
which tells us the max depth of the tree is 4