# 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

## Leave a Reply