Given a parent array P, where P[i] indicates the parent of the 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
- Start at each node and keep going to its parent until we reach -1.
- Also, keep track of the maximum height between all nodes.
Implementation:
C++
// C++ program to find the height of the generic// tree(n-ary tree) if parent array is given#include <bits/stdc++.h>using namespace std;// function to find the height of treeint 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 programint 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 givenimport 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 codeif __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 givenusing 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. |
Javascript
<script>// JavaScript program to find the height of// the generic tree(n-ary tree) if// parent array is given // function to find the height of tree function findHeight(parent,n) { let res = 0; // Traverse each node for (let i = 0; i < n; i++) { // traverse to parent until -1 // is reached let p = i, current = 1; while (parent[p] != -1) { current++; p = parent[p]; } res = Math.max(res, current); } return res; } // Driver program let parent=[-1, 0, 1, 6, 6, 0, 0, 2, 7]; let n = parent.length; let height = findHeight(parent, n); document.write("Height of the " + "given tree is: " + height); // This code is contributed by unknown2108</script> |
Output:
Height of the given tree is: 5
Time Complexity : O( N^2 )
Space Complexity : O( 1 )
Optimized approach: We use dynamic programming. We store the height from root to each node in an array. So, if we know the height of the root to a node, then we can get the height from the root to the node child by simply adding 1.
Implementation:
CPP
// C++ program to find the height of the generic// tree(n-ary tree) if parent array is given#include <bits/stdc++.h>using namespace std;// function to fill the height vectorint rec(int i, int parent[], vector<int> height){ // if we have reached root node the // return 1 as height of root node if (parent[i] == -1) { return 1; } // if we have calculated height of a // node then return if if (height[i] != -1) { return height[i]; } // height from root to a node = height // from root to nodes parent + 1 height[i] = rec(parent[i], parent, height) + 1; // return nodes height return height[i];}// function to find the height of treeint findHeight(int* parent, int n){ int res = 0; // vector to store heights of all nodes vector<int> height(n, -1); for (int i = 0; i < n; i++) { res = max(res, rec(i, parent, height)); } return res;}// Driver programint 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 givenimport java.io.*;import java.util.*;class GFG { // function to fill the height vector static int rec(int i, int parent[], int[] height) { // if we have reached root node the // return 1 as height of root node if (parent[i] == -1) { return 1; } // if we have calculated height of a // node then return if if (height[i] != -1) { return height[i]; } // height from root to a node = height // from root to nodes parent + 1 height[i] = rec(parent[i], parent, height) + 1; // return nodes height return height[i]; } // function to find the height of tree static int findHeight(int[] parent, int n) { int res = 0; // vector to store heights of all nodes int height[]=new int[n]; Arrays.fill(height,-1); for (int i = 0; i < n; i++) { res = Math.max(res, rec(i, parent, height)); } return res; } // Driver program public static 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 avanitrachhadiya2155 |
Python3
# Python3 program to find the height of the generic# tree(n-ary tree) if parent array is given# function to fill the height vectordef rec(i, parent, height): # if we have reached root node the # return 1 as height of root node if (parent[i] == -1): return 1 # if we have calculated height of a # node then return if if (height[i] != -1): return height[i] # height from root to a node = height # from root to nodes parent + 1 height[i] = rec(parent[i], parent, height) + 1 # return nodes height return height[i]# function to find the height of treedef findHeight(parent, n): res = 0 # vector to store heights of all nodes height = [-1]*(n) for i in range(n): res = max(res, rec(i, parent, height)) return res# Driver programif __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 mohit kumar 29. |
C#
// C# program to find the height of the generic// tree(n-ary tree) if parent array is givenusing System;public class GFG{ // function to fill the height vector static int rec(int i, int[] parent, int[] height) { // if we have reached root node the // return 1 as height of root node if (parent[i] == -1) { return 1; } // if we have calculated height of a // node then return if if (height[i] != -1) { return height[i]; } // height from root to a node = height // from root to nodes parent + 1 height[i] = rec(parent[i], parent, height) + 1; // return nodes height return height[i]; } // function to find the height of tree static int findHeight(int[] parent, int n) { int res = 0; // vector to store heights of all nodes int[] height = new int[n]; Array.Fill(height, -1); for (int i = 0; i < n; i++) { res = Math.Max(res, rec(i, parent, height)); } 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 ab2127 |
Javascript
<script>// Javascript program to find the height of the generic// tree(n-ary tree) if parent array is given// function to fill the height vectorfunction rec(i,parent,height){ // if we have reached root node the // return 1 as height of root node if (parent[i] == -1) { return 1; } // if we have calculated height of a // node then return if if (height[i] != -1) { return height[i]; } // height from root to a node = height // from root to nodes parent + 1 height[i] = rec(parent[i], parent, height) + 1; // return nodes height return height[i];}// function to find the height of treefunction findHeight(parent,n){ let res = 0; // vector to store heights of all nodes let height=new Array(n); for(let i=0;i<n;i++) { height[i]=-1; } for (let i = 0; i < n; i++) { res = Math.max(res, rec(i, parent, height)); } return res;}// Driver programlet parent=[-1, 0, 1, 6, 6, 0, 0, 2, 7];let n=parent.length;let height = findHeight(parent, n);document.write("Height of the given tree is: "+height+"<br>"); // This code is contributed by patel2127</script> |
Output:
Height of the given tree is: 5
Time complexity :- O(n)
Space complexity :- O(n)
This article is contributed by Prakriti Gupta. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!