We are given a tree of size n as array parent[0..n-1] where every index i in parent[] represents a node and the value at i represents the immediate parent of that node. For root node value will be -1. Find the height of the generic tree given the parent links.

Examples:

Input : parent[] = {-1, 0, 0, 0, 3, 1, 1, 2} Output : 2 Input : parent[] = {-1, 0, 1, 2, 3} Output : 4

Here, generic tree is sometimes also called as N-ary tree or N-way tree where N denotes the maximum number of child a node can have. In this problem array represents n number of nodes in the tree.

**Approach 1:**

One solution is to traverse up the tree from node till root node is reached with node value -1. While Traversing for each node store maximum path length.

Time Complexity of this solution is **O(n^2)**.

**Approach 2:**

Build graph for N-ary Tree in O(n) time and apply BFS on the stored graph in O(n) time and while doing BFS store maximum reached level. This solution does two iterations to find the height of N-ary tree.

// C++ code to find height of N-ary // tree in O(n) #include <bits/stdc++.h> #define MAX 1001 using namespace std; // Adjacency list to // store N-ary tree vector<int> adj[MAX]; // Build tree in tree in O(n) int build_tree(int arr[], int n) { int root_index = 0; // Iterate for all nodes for (int i = 0; i < n; i++) { // if root node, store index if (arr[i] == -1) root_index = i; else { adj[i].push_back(arr[i]); adj[arr[i]].push_back(i); } } return root_index; } // Applying BFS int BFS(int start) { // map is used as visited array map<int, int> vis; queue<pair<int, int> > q; int max_level_reached = 0; // height of root node is zero q.push({ start, 0 }); // p.first denotes node in adjacency list // p.second denotes level of p.first pair<int, int> p; while (!q.empty()) { p = q.front(); vis[p.first] = 1; // store the maximum level reached max_level_reached = max(max_level_reached, p.second); q.pop(); for (int i = 0; i < adj[p.first].size(); i++) // adding 1 to previous level // stored on node p.first // which is parent of node adj[p.first][i] // if adj[p.first][i] is not visited if (!vis[adj[p.first][i]]) q.push({ adj[p.first][i], p.second + 1 }); } return max_level_reached; } // Driver Function int main() { // node 0 to node n-1 int parent[] = { -1, 0, 1, 2, 3 }; // Number of nodes in tree int n = sizeof(parent) / sizeof(parent[0]); int root_index = build_tree(parent, n); int ma = BFS(root_index); cout << "Height of N-ary Tree=" << ma; return 0; }

**Output:**

Height of N-ary Tree=4

Time Complexity of this solution is **O(2n) **which converges to O(n) for very large n.

**Approach 3:**

We can find the height of N-ary Tree in only one iteration. We visit nodes from 0 to n-1 iteratively and mark the unvisited ancestors recursively if they are not visited before till we reach a node which is visited or we reach root node. If we reach visited node while traversing up the tree using parent links, then we use its height and will not go further in recursion.

**Explanation For Example 1::**

For **node 0** : Check for Root node is true,

Return 0 as height, Mark node 0 as visited

For **node 1** : Recur for immediate ancestor, i.e 0, which is already visited

So, Use it’s height and return height(node 0) +1

Mark node 1 as visited

For **node 2** : Recur for immediate ancestor, i.e 0, which is already visited

So, Use it’s height and return height(node 0) +1

Mark node 2 as visited

For **node 3** : Recur for immediate ancestor, i.e 0, which is already visited

So, Use it’s height and return height(node 0) +1

Mark node 3 as visited

For **node 4** : Recur for immediate ancestor, i.e 3, which is already visited

So, Use it’s height and return height(node 3) +1

Mark node 3 as visited

For **node 5** : Recur for immediate ancestor, i.e 1, which is already visited

So, Use it’s height and return height(node 1) +1

Mark node 5 as visited

For **node 6** : Recur for immediate ancestor, i.e 1, which is already visited

So, Use it’s height and return height(node 1) +1

Mark node 6 as visited

For **node 7** : Recur for immediate ancestor, i.e 2, which is already visited

So, Use it’s height and return height(node 2) +1

Mark node 7 as visited

Hence, we processed each node in N-ary tree only once.

// C++ code to find height of N-ary // tree in O(n) (Efficient Approach) #include <bits/stdc++.h> using namespace std; // Recur For Ancestors of node and // store height of node at last int fillHeight(int p[], int node, int visited[], int height[]) { // If root node if (p[node] == -1) { // mark root node as visited visited[node] = 1; return 0; } // If node is already visited if (visited[node]) return height[node]; // Visit node and calculate its height visited[node] = 1; // recur for the parent node height[node] = 1 + fillHeight(p, p[node], visited, height); // return calculated height for node return height[node]; } int findHeight(int parent[], int n) { // To store max height int ma = 0; // To check whether or not node is visited before int visited[n]; // For Storing Height of node int height[n]; memset(visited, 0, sizeof(visited)); memset(height, 0, sizeof(height)); for (int i = 0; i < n; i++) { // If not visited before if (!visited[i]) height[i] = fillHeight(parent, i, visited, height); // store maximum height so far ma = max(ma, height[i]); } return ma; } // Driver Function int main() { int parent[] = { -1, 0, 0, 0, 3, 1, 1, 2 }; int n = sizeof(parent) / sizeof(parent[0]); cout << "Height of N-ary Tree = " << findHeight(parent, n); return 0; }

**Output:**

Height of N-ary Tree = 2

**Time Complexity:** O(n)

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

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

more link ADS

Smart Retail, Smart Agriculture, Smart supply Chain, Smart Health, Smart energy, Smart City

Blockchain, bitcoin, ethereum, blockchain technology, cryptocurrencies

Information Security, latest Hacking News, Cyber Security, Network Sec

Information Security, latest Hacking News, Cyber Security, Network Security

Blog! Development Software and Application Mobile

Development apps, Android, Ios anh Tranning IT, data center, hacking

Car News, Reviews, Pricing for New & Used Cars, car reviews and news, concept cars

Travel Blog is a unique free online travel diary for travellers across the world.