Table of Contents
Problem Statement
“Height of a generic tree from parent array” problem states that you are given a tree with n vertices as an array par[0…n-1]. Here every index i in par[] represents a node and the value at i represents the immediate parent of that node. For the root node with no parent, the value for it in par[] array would be -1. Now we need to find the height of the tree given the parent linkages.
Consider the par[] array given below:
The tree constructed using these par[] array linkages is given below:
Note: height of the tree cannot go beyond 100 units.
Example
[-1 0 0 1 2 2 4]
3
Explanation: number of edges on the longest path is 3.
[-1 0 0 1 1 2 2 3 3 4 7]
4
Explanation: number of edges on the longest path (0->1->3->7->10) is 4.
Types of Solution
- Breadth-First Search
- Dynamic Programming
Breadth-First Search
Approach to find Height of a generic tree from parent array
To solve this problem we will construct a tree (graph data structure) using the given par[] array. Now we perform BFS starting from the root node and find the longest path (or distance of the furthest vertex) along the tree path. So, the value of this distance itself is said to be the height of the tree. BFS is nothing but a graph traversal algorithm that traverses the whole graph. Breadth-First Search works such that the nodes which are nearest to the current node are traversed before the nodes having more distance. This way we are able to find the distance of each node from the root. And the node with the largest distance is said to be the node at the height of the tree.
Algorithm
1. Construct the directed graph using the par[] array values. 2. The edges in graph should be directed from node par[i] to i. i.e, par[i] --> i. 3. The root node has no parent and hence, no incoming edge. 4. Now starting from the root node, perform BFS, and calculate distance of each of the nodes in the tree from the root node itself. 5. The largest distance value is the height of the tree.
The algorithm is depicted below:
Code
C++ Program to find height of a generic tree from parent array
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// perform BFS to calculate Height
int BFS(vector <int> par)
{
int root;
int n = par.size();
vector <int> graph[n];
// construct graph from given parent array
for(int i=0;i<n;i++)
{
if(par[i] != -1)
graph[par[i]].push_back(i);
else
root = i;
}
// to store distance of each node from the root
vector <int> distance(n,0);
// create BFS queue
queue <int> q;
// insert the root node
q.push(root);
// Begin BFS & calculate distance of each node from root
while(!q.empty())
{
int front = q.front();
q.pop();
for(auto i : graph[front])
{
distance[i] = distance[front] + 1;
q.push(i);
}
}
// return height of the Tree
return *max_element(distance.begin(),distance.end());
}
int main()
{
// define parent array
vector <int> par = {-1,0,0,1,2,2,4};
cout<<"Height of the Tree : "<<BFS(par)<<endl;
return 0;
}Height of the Tree : 3
Java Program to find Height of a generic tree from parent array
import java.util.*;
import java.io.*;
class TutorialCup
{
// perform BFS to calculate Height
static int BFS(int [] par)
{
int root = 0;
int n = par.length;
ArrayList <ArrayList <Integer>> graph = new ArrayList<ArrayList<Integer>>();
// construct graph from given parent array
for(int i=0;i<n;i++)
{
graph.add(new ArrayList<Integer>());
if(par[i] != -1)
graph.get(par[i]).add(i);
else
root = i;
}
// to store distance of each node from the root
int distance[] = new int[n];
// create BFS queue
Queue <Integer> q = new LinkedList<>();
// insert the root node
q.add(root);
// Begin BFS & calculate distance of each node from root
while(!q.isEmpty())
{
int front = q.poll();
Iterator itr = graph.get(front).iterator();
while(itr.hasNext())
{
int i = (Integer)itr.next();
distance[i] = distance[front] + 1;
q.add(i);
}
}
// return height of the Tree
int height = 0;
for(int i=0;i<distance.length;i++)
height = Math.max(height,distance[i]);
return height;
}
public static void main (String[] args)
{
// define parent array
int [] par = {-1,0,0,1,2,2,4};
System.out.println("Height of the Tree : "+BFS(par));
}
}Height of the Tree : 3
Complexity Analysis
Time Complexity
T(n) = O(V+E) = O(2V-1) = O(V). Here we have performed a breadth-first search which will cover the whole tree thus covering a total of V vertices. Thus giving us a linear time complexity.
Space Complexity
A(n) = O(V), for the BFS queue & graph-tree created. In the worst case, we can have a star tree, where all the nodes have the same parent other than the root. Thus in that case, worst space complexity will be achieved which will be O(V).
where,
V = number of vertices in the tree.
E = number of edges in a tree = V-1
Dynamic Programming
Approach to find Height of a generic tree from parent array
In a Tree of N nodes, visit each node in order from 0 to N-1. For each node calculate it’s height using the function findHeight( ) (height of a node is the number of edges between that particular node and root node).
Before calculating the height of a node, the height of all it’s ancestor nodes need to be calculated recursively. The findDistance( ) does this task recursively. After calculating the height of a node in the tree. It should be marked as visited (visited[] array is used for this purpose).
Algorithm
1. Define two functions findDistance( ) & findHeight( ) for calculating height of each node in the tree. 2. Visit each node iteratively in order from 0 to V-1 (where V = number of vertices). 3. For a particular node, calculate heights of all it's ancestors recursively before the calculating height of the node itself, this is done using findDistance() recursive function. 4. every ancestor node visited should be marked as visited (using visited[ ] array). 5. Return the maximum value in the height[ ]. 6. steps 1 to 5 are encapsulated in findHeight( ) function.
Code
C++ Program to find Height of a generic tree from parent array
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// function to find height of node - i from tree root
int findDistance(vector <int> par, int i, vector <bool> &visited, vector <int> &height)
{
// if root node is encountered
if(par[i] == -1)
{
visited[i] = true;
return 0;
}
// if node is already visited
// return it's calculated height
if(visited[i])
return height[i];
// if a node is not visited
// below steps are executed
// mark node visited
visited[i] = true;
// calculate height of node
height[i] = 1+findDistance(par,par[i],visited,height);
// return height after calculation
return height[i];
}
// function to calculate maximum height
int findHeight(vector <int> par)
{
int maxHeight = 0;
int n = par.size();
// visited array is used to check if a node is visited
vector <bool> visited(n,false);
// calculate height of each node in the tree
vector <int> height(n,0);
// traverse each node of the tree
// evaluate height of each node & store maximum of all heights
for(int i=0;i<n;i++)
{
height[i] = findDistance(par,i,visited,height);
maxHeight = max(maxHeight,height[i]);
}
// return maximum of all heights
return maxHeight;
}
int main()
{
// define parent array
vector <int> par = {-1,0,0,1,2,2,4};
cout<<"Height of the Tree : "<<findHeight(par)<<endl;
return 0;
}Height of the Tree : 3
Java Program to find Height of a generic tree from parent array
import java.util.*;
import java.io.*;
class TutorialCup
{
// function to find height of node - i from tree root
static int findDistance(int [] par, int i, boolean [] visited, int [] height)
{
// if root node is encountered
if(par[i] == -1)
{
visited[i] = true;
return 0;
}
// if node is already visited
// return it's calculated height
if(visited[i] == true)
return height[i];
// if a node is not visited
// below steps are executed
// mark node visited
visited[i] = true;
// calculate height of node
height[i] = 1+findDistance(par,par[i],visited,height);
// return height after calculation
return height[i];
}
// function to calculate maximum height
static int findHeight(int [] par)
{
int maxHeight = 0;
int n = par.length;
// visited array is used to check if a node is visited
boolean [] visited = new boolean[n];
// calculate height of each node in the tree
int [] height = new int[n];
// traverse each node of the tree
// evaluate height of each node & store maximum of all heights
for(int i=0;i<n;i++)
{
height[i] = findDistance(par,i,visited,height);
maxHeight = Math.max(maxHeight,height[i]);
}
// return maximum of all heights
return maxHeight;
}
public static void main (String[] args)
{
// define parent array
int [] par = {-1,0,0,1,2,2,4};
System.out.println("Height of the Tree : "+findHeight(par));
}
}Height of the Tree : 3
Complexity Analysis
Time Complexity
O(N), because here also we will be traversing all the nodes of the tree. Since we will be traversing all the nodes of the tree. Because of that, we achieved linear time complexity O(N) where N denoted the number of nodes in the tree.
Space Complexity
O(N), we need to store the height for each of the nodes. Since that will be used when by the children of the current node. Thus the algorithm has linear space complexity.