Hey ninjas, this blog will explain how you can find the height of a generic tree, also known as N- ary tree or the N-way tree. We will discuss the problem statement in two approaches, optimal and non-optimal problems. We will also implement the problem in different programming languages.

Problem statement

The problem statement is that we will be given an array name parent with n number of elements that build a tree. Each index i in the parent array represents a node in the tree, and the value at the ith index represents the immediate parent of the i index.

We need to find the height of this generic tree given as a parent array. A generic or N-way tree is a tree in which a node can have N nodes. A tree's height is the most extended root node to the leaf path in the tree.

Sample Example

Input: [-1,0,0,1,1,1,5,2]

Output: The height of this generic tree given as parent array is: 3

Explanation:

Approach 1

The root node, which has node value -1, can be reached by moving up the tree from the node. While Traversing, the maximum path length will be stored for each node. Time complexity is O(n^2).

Approach 2

Now we will discuss an optimal approach, and in this, we will traverse the tree from 0 to n times, but we will mark the nodes recursively, so if we revisit this marked node, we can end our traversal for that route and calculate the height till that node and return it. After that, we will compare the previous height and current height and return the maximum height at the end of the traversal of all nodes to the main function

Algorithm

Declare the parent array.

Calculate the size of the parent array.

Call getHeight( ) with arguments parent array and size n.

Declare the Maxheight variable to store the maximum height.

Declare and initialize marked and height array with n times 0 elements.

For loop till i<n where i=0.

Check if the element at the i index is visited or not.

Call nodeHeight( ) to calculate height for each node.

Loop end

In nodeHeight( ):

Check if the current element is root or not.

Check if the current element is visited or not.

Marked the node.

Recursively call nodeHeight( ) until any one condition given in function is true.

Return to nodeHeight( ) call in getHeight( ) function.

Compare the heights.

Return maximum height.

End.

Implementation

C++

#include <bits/stdc++.h>
using namespace std;
int nodeHeight(int tree[], int node, int marked[],
int height[]) {
/* Checking if it is a root node or not*/
if (tree[node] == -1) {
/* Marking the root node of tree*/
marked[node] = 1;
return 0;
}
/* Checking if the node is visited or not*/
if (marked[node])
return height[node];
/* Marking the node for future*/
marked[node] = 1;
/* Applying recursion till we get marked node or root node*/
height[node] = 1 + nodeHeight(tree, tree[node],
marked, height);
return height[node];
}
int getHeight(int parent[], int n) {
/* To store max height*/
int Maxheight = 0;
/* Declaring height array and marked node array*/
int marked[n], height[n];
/* Initializing both marked and height
array with n-0 elements*/
for (int i = 0; i < n; i++) {
marked[i] = 0;
height[i] = 0;
}
for (int i = 0; i < n; i++) {
/* If the node is not marked*/
if (!marked[i])
height[i] = nodeHeight(parent, i,
marked, height);
/* Comparing and storing max height */
Maxheight = max(Maxheight, height[i]);
}
return Maxheight;
}
int main() {
int parent[] = { -1,0,0,0,1,1,1,2,3};
int n = sizeof(parent) / sizeof(parent[0]);
cout << "The height of this generic tree given as parent array is: " << getHeight(parent, n);
return 0;
}

JAVA

import java.util.*;
class Main {
static int nodeHeight(int tree[], int node,
int marked[], int height[]) {
/* Checking if it is a root node or not*/
if (tree[node] == -1) {
/* Marking the root node of the tree*/
marked[node] = 1;
return 0;
}
/* Checking if a node is visited or not*/
if (marked[node] == 1)
return height[node];
/* Marking the node for future*/
marked[node] = 1;
/* Applying recursion till we get marked node or root node*/
height[node] = 1 + nodeHeight(tree, tree[node],
marked, height);
return height[node];
}
static int getHeight(int parent[], int n) {
/* To store max height*/
int Maxheight = 0;
/* Declaring height array and marked node array*/
int[] marked = new int[n];
int[] height = new int[n];
/* Initializing both marked and height
array with n-0 elements*/
for (int i = 0; i < n; i++) {
marked[i] = 0;
height[i] = 0;
}
for (int i = 0; i < n; i++) {
/* If the node is not marked*/
if (marked[i] != 1)
height[i] = nodeHeight(parent, i,
marked, height);
/* Comparing and storing max height */
Maxheight = Math.max(Maxheight, height[i]);
}
return Maxheight;
}
public static void main(String[] args) {
int parent[] = {-1,0,0,0,1,1,1,2,3};
int n = parent.length;
System.out.println("The height of this generic tree given as parent array is: " +
getHeight(parent, n));
}
}

PYTHON

def nodeHeight(tree, node, marked, height):
# Checking if it is root node or not
if (tree[node] == -1):
# marking the root node of tree
marked[node] = 1
return 0
# Checking if the node is visited or not
if (marked[node]):
return height[node]
# Marking the node for future
marked[node] = 1
# Applying recursion till we get marked node or root node
height[node] = 1 + nodeHeight(tree, tree[node], marked, height)
return height[node]
def getHeight(parent, n):
#To store max-height
Maxheight = 0
# Declaring height array and marked node array
marked = [0] * n
height = [0] * n
for i in range(n):
# If the node is not marked
if (not marked[i]):
height[i] = nodeHeight(parent, i,marked, height)
# Comparing and storing max-height
Maxheight = max(Maxheight, height[i])
return Maxheight
if __name__ == '__main__':
parent = [-1,0,0,0,1,1,1,2,3]
n = len(parent)
print("The height of this generic tree given as parent array is: ", getHeight(parent, n))

Output

Complexity Analysis

Time Complexity

O(n) is the time complexity we calculated from the above implementation, where n is the number of elements present in the parent array.

Space Complexity

Space complexity is O(n) because of the marked height and parent array size. All three of them have size n. total space complexity is O(3n); neglecting the constant, we got O(n).

A generic tree or N- way tree is the tree in which a node can have N number of children nodes.

What does the parent array represent?

A parent array is an array that contains an immediate parent for the Ith index of the given array. For example:

[-1,0,1,1,2] in this array 0 is the root node for index 1.

What are the two ways to measure the height of a tree?

We can measure a tree's height in terms of nodes or in terms of vertices present in the longest route of that tree.

How do you represent the root node in the parent array?

If there is a -1 element present at index i, then that particular index is marked as the root node in the parent array.

What is the difference between a generic tree and a binary tree?

In a binary tree, a node can have at most 2 children nodes but in a generic tree, a node can have N- number of children nodes.

Conclusion

In this article, we have discussed how to find the height of a generic tree from a parent array with implementation in three different programming languages. Also, we have seen the time complexity for the. We have also discussed the brute force approach, which is not an optimal solution but is better known.

For more Tree data structure articles, you can refer following links: