Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement 
2.1.
Sample Example
3.
Approach 1
4.
Approach 2
4.1.
Algorithm
4.2.
Implementation
4.2.1.
C++
4.2.2.
JAVA
4.2.3.
PYTHON
4.2.4.
Output
5.
Complexity Analysis
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently Asked Questions
6.1.
What do you mean by a generic tree?
6.2.
What does the parent array represent?
6.3.
What are the two ways to measure the height of a tree?
6.4.
How do you represent the root node in the parent array?
6.5.
What is the difference between a generic tree and a binary tree?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find the Height of a Generic Tree from Parent Array

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

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:

explanation

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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:

 

Recommended problems -

 

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.

Live masterclass