Open In App

Height of n-ary tree if parent array is given

Last Updated : 09 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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
  1. Start at each node and keep going to its parent until we reach -1. 
  2. 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 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.
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 )
Auxiliary Space: 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 vector
int 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 tree
int 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 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.*;
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
Python 
# Python3 program to find the height of the generic
# tree(n-ary tree) if parent array is given

# function to fill the height vector
def 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 tree
def 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 program
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 mohit kumar 29.
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 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 vector
function 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 tree
function 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 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+"<br>");
    

// This code is contributed by patel2127
</script>

Output
Height of the given tree is: 5

Time complexity :- O(n) 
Auxiliary Space:- O(n) 



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Find the cousins of a given element in an N-ary tree
Next Article
Print siblings of a given Node in N-ary Tree

Similar Reads

Height of a generic tree from parent array
We are given a tree of size n as array parent[0..n-1] where every index i in the parent[] represents a node and the value at i represents the immediate parent of that node. For root node value will be -1. Find the height of the generic tree given the parent links. Examples: Input : parent[] = {-1, 0, 0, 0, 3, 1, 1, 2} Output : 2 Input : parent[] =
15+ min read
Find Height of Binary Tree represented by Parent array
A given array represents a tree in such a way that the array value gives the parent node of that particular index. The value of the root node index would always be -1. Find the height of the tree. The height of a Binary Tree is the number of nodes on the path from the root to the deepest leaf node, and the number includes both root and leaf. Input:
13 min read
Number of leaf nodes in a perfect N-ary tree of height K
Find the number of leaf nodes in a perfect N-ary tree of height K. Note: As the answer can be very large, return the answer modulo 109+7. Examples: Input: N = 2, K = 2Output: 4Explanation: A perfect Binary tree of height 2 has 4 leaf nodes. Input: N = 2, K = 1Output: 2Explanation: A perfect Binary tree of height 1 has 2 leaf nodes. Approach: This p
4 min read
Check if the given n-ary tree is a binary tree
Given an n-ary tree, the task is to check whether the given tree is binary or not. Examples: Input: A / \ B C / \ \ D E F Output: Yes Input: A / | \ B C D \ F Output: No Approach: Every node in a binary tree can have at most 2 children. So, for every node of the given tree, count the number of children and if for any node the count exceeds 2 then p
6 min read
Count of nodes in given N-ary tree such that their subtree is a Binary Tree
Given an N-ary tree root, the task is to find the count of nodes such that their subtree is a binary tree. Example: Input: Tree in the image below Output: 11Explanation: The nodes such that there subtree is a binary tree are {2, 8, 10, 6, 7, 3, 1, 9, 5, 11, 12}. Input: Tree in the image below Output: 9 Approach: The given problem can be solved by u
11 min read
Find parent of given node in a Binary Tree with given postorder traversal
Given two integers N and K where N denotes the height of a binary tree, the task is to find the parent of the node with value K in a binary tree whose postorder traversal is first [Tex]2^{N}-1 [/Tex] natural numbers [Tex](1, 2, ... 2^{N}-1) [/Tex] For N = 3, the Tree will be - 7 / \ 3 6 / \ / \ 1 2 4 5 Examples: Input: N = 4, K = 5 Output: 6 Explan
9 min read
Construct Binary Tree from given Parent Array representation | Iterative Approach
Given an array that represents a tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of given Binary Tree from this given representation
12 min read
Construct Binary Tree from given Parent Array representation
Given an array that represents a tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of given Binary Tree from this given representation
15+ min read
Build a segment tree for N-ary rooted tree
Prerequisite: Segment tree and depth first search.In this article, an approach to convert an N-ary rooted tree( a tree with more than 2 children) into a segment tree is discussed which is used to perform a range update queries. Why do we need a segment tree when we already have an n-ary rooted tree? Many times, a situation occurs where the same ope
15+ min read
Remove all leaf nodes from a Generic Tree or N-ary Tree
Given a Generic tree, the task is to delete the leaf nodes from the tree. Examples: Input: 5 / / \ \ 1 2 3 8 / / \ \ 15 4 5 6 Output: 5 : 1 2 3 1 : 2 : 3 : Explanation: Deleted leafs are: 8, 15, 4, 5, 6 Input: 8 / | \ 9 7 2 / | \ | / / | \ \ 4 5 6 10 11 1 2 2 3 Output: 8: 9 7 2 9: 7: 2: Approach: Follow the steps given below to solve the problem Co
9 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox