Tutorialspoint.dev

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  



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 <bits/stdc++.h>
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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter