# Height of n-ary tree if parent array is given

Given a parent array P, where P[i] indicates the parent of ith node in the tree(assume parent of root node id indicated with -1). Find the height of the tree.

Examples:

```Input : array[] = [-1 0 1 6 6 0 0 2 7]
Output : height = 5
Tree formed is:
0
/ |
5  1  6
/   |
2    4  3
/
7
/
8
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

1. Start at each node and keep going to its parent until we reach -1.
2. Also keep track of the maximum height among all nodes.

## C++

 `// C++ program to find the height of the generic ` `// tree(n-ary tree) if parent array is given ` `#include ` `using` `namespace` `std; ` ` `  `// function to find the height of tree ` `int` `findHeight(``int``* parent, ``int` `n) ` `{ ` `    ``int` `res = 0; ` ` `  `    ``// Traverse each node ` `    ``for` `(``int` `i = 0; i < n; i++) { ` `              `  `        ``// traverse to parent until -1  ` `        ``// is reached ` `        ``int` `p = i, current = 1; ` `        ``while` `(parent[p] != -1) { ` `            ``current++; ` `            ``p = parent[p]; ` `        ``} ` ` `  `        ``res = max(res, current); ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `parent[] = {-1, 0, 1, 6, 6, 0, 0, 2, 7}; ` `    ``int` `n = ``sizeof``(parent)/``sizeof``(parent[0]); ` `    ``int` `height = findHeight(parent, n); ` `    ``cout << ``"Height of the given tree is: "` `         ``<< height << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find the height of ` `// the generic tree(n-ary tree) if  ` `// parent array is given ` `import` `java.io.*;  ` ` `  `public` `class` `GFG { ` `     `  `    ``// function to find the height of tree ` `    ``static` `int` `findHeight(``int` `[]parent, ``int` `n) ` `    ``{ ` `        ``int` `res = ``0``; ` `     `  `        ``// Traverse each node ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``{ ` `                 `  `            ``// traverse to parent until -1  ` `            ``// is reached ` `            ``int` `p = i, current = ``1``; ` `            ``while` `(parent[p] != -``1``)  ` `            ``{ ` `                ``current++; ` `                ``p = parent[p]; ` `            ``} ` `     `  `            ``res = Math.max(res, current); ` `        ``} ` `        ``return` `res; ` `    ``} ` `     `  `    ``// Driver program ` `    ``static` `public` `void` `main (String[] args) ` `    ``{ ` `        ``int` `[]parent = {-``1``, ``0``, ``1``, ``6``, ``6``, ``0``, ` `                                    ``0``, ``2``, ``7``}; ` `        ``int` `n = parent.length; ` `         `  `        ``int` `height = findHeight(parent, n); ` `         `  `        ``System.out.println(``"Height of the "` `             ``+ ``"given tree is: "` `+ height); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## Python3

 `# Python program to find the height of the generic  ` `# tree(n-ary tree) if parent array is given  ` ` `  `# function to find the height of tree  ` `def` `findHeight(parent, n):  ` ` `  `    ``res ``=` `0` ` `  `    ``# Traverse each node  ` `    ``for` `i ``in` `range``(n):            ` `        ``# traverse to parent until -1  ` `        ``# is reached  ` `        ``p ``=` `i ` `        ``current ``=` `1` `        ``while` `(parent[p] !``=` `-``1``): ` `            ``current``+``=``1` `            ``p ``=` `parent[p]  ` `        ``res ``=` `max``(res, current)  ` `    ``return` `res  ` ` `  `     `  `# Driver code ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``parent ``=` `[``-``1``, ``0``, ``1``, ``6``, ``6``, ``0``, ``0``, ``2``, ``7``] ` `    ``n ``=` `len``(parent)  ` `    ``height ``=` `findHeight(parent, n)  ` `    ``print``(``"Height of the given tree is:"``, height) ` ` `  `# This code is contributed by SHUBHAMSINGH10 `

## C#

 `// C# program to find the height of ` `// the generic tree(n-ary tree) if ` `// parent array is given ` `using` `System; ` ` `  `public` `class` `GFG { ` `     `  `    ``// function to find the height of tree ` `    ``static` `int` `findHeight(``int` `[]parent, ``int` `n) ` `    ``{ ` `        ``int` `res = 0; ` `     `  `        ``// Traverse each node ` `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``{ ` `                 `  `            ``// traverse to parent until -1  ` `            ``// is reached ` `            ``int` `p = i, current = 1; ` `            ``while` `(parent[p] != -1) ` `            ``{ ` `                ``current++; ` `                ``p = parent[p]; ` `            ``} ` `     `  `            ``res = Math.Max(res, current); ` `        ``} ` `         `  `        ``return` `res; ` `    ``} ` `     `  `    ``// Driver program ` `    ``static` `public` `void` `Main () ` `    ``{ ` `        ``int` `[]parent = {-1, 0, 1, 6, 6, 0, ` `                                  ``0, 2, 7}; ` `        ``int` `n = parent.Length; ` `         `  `        ``int` `height = findHeight(parent, n); ` `         `  `        ``Console.WriteLine (``"Height of the "` `             ``+ ``"given tree is: "` `+ height); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

Output:

```Height of the given tree is: 5
```

## tags:

Tree n-ary-tree Tree