Find the Height of a Generic Tree from Parent Array

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).

Check out this problem - Find Duplicate In Array

Frequently Asked Questions

What do you mean by a generic tree?

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:

• Closest element to a target value in a binary search tree
• Check if a binary tree has duplicate values
• Maximum level sum in a binary tree

Recommended problems -

• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k
• Shortest subarray with sum at least k

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.