Find Height of Binary Tree represented by Parent array - GeeksforGeeks
If we take a closer look, we can observe that depth of every node is evaluated only once.
Iterative version:
https://gist.github.com/sumitdanish/ec2c7c2fa4306d2bb432
Not efficient:
http://code.geeksforgeeks.org/O8pJpE
public static int getDepth(int arr[])
{
int i = 0;
int j = 0;
int depth = 0;
int maxDepth = 0;
while (i < arr.length)
{
j = i;
depth = 0;
while (j != -1)
{
j = arr[j];
depth++;
}
if (depth > maxDepth)
{
maxDepth = depth;
}
i++;
}
return depth;
}
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.
Height of a Binary Tree is number of nodes on the path from root to the deepest leaf node, the number includes both root and leaf.
Height of a Binary Tree is number of nodes on the path from root to the deepest leaf node, the number includes both root and leaf.
Input: parent[] = {1 5 5 2 2 -1 3} Output: 4 The given array represents following Binary Tree 5 / \ 1 2 / / \ 0 3 4 / 6 Input: parent[] = {-1, 0, 0, 1, 1, 3, 5}; Output: 5 The given array represents following Binary Tree 0 / \ 1 2 / \ 3 4 / 5 / 6
An efficient solution can solve the above problem in O(n) time. The idea is to first calculate depth of every node and store in an array depth[]. Once we have depths of all nodes, we return maximum of all depths.
1) Find depth of all nodes and fill in an auxiliary array depth[].
2) Return maximum value in depth[].
1) Find depth of all nodes and fill in an auxiliary array depth[].
2) Return maximum value in depth[].
Following are steps to find depth of a node at index i.
1) If it is root, depth[i] is 1.
2) If depth of parent[i] is evaluated, depth[i] is depth[parent[i]] + 1.
3) If depth of parent[i] is not evaluated, recur for parent and assign depth[i] as depth[parent[i]] + 1 (same as above).
1) If it is root, depth[i] is 1.
2) If depth of parent[i] is evaluated, depth[i] is depth[parent[i]] + 1.
3) If depth of parent[i] is not evaluated, recur for parent and assign depth[i] as depth[parent[i]] + 1 (same as above).
// This function fills depth of i'th element in parent[]. The depth is
// filled in depth[i].
void
fillDepth(
int
parent[],
int
i,
int
depth[])
{
// If depth[i] is already filled
if
(depth[i])
return
;
// If node at index i is root
if
(parent[i] == -1)
{
depth[i] = 1;
return
;
}
// If depth of parent is not evaluated before, then evaluate
// depth of parent first
if
(depth[parent[i]] == 0)
fillDepth(parent, parent[i], depth);
// Depth of this node is depth of parent plus 1
depth[i] = depth[parent[i]] + 1;
}
// This function returns height of binary tree represented by
// parent array
int
findHeight(
int
parent[],
int
n)
{
// Create an array to store depth of all nodes/ and
// initialize depth of every node as 0 (an invalid
// value). Depth of root is 1
int
depth[n];
for
(
int
i = 0; i < n; i++)
depth[i] = 0;
// fill depth of all nodes
for
(
int
i = 0; i < n; i++)
fillDepth(parent, i, depth);
// The height of binary tree is maximum of all depths.
// Find the maximum value in depth[] and assign it to ht.
int
ht = depth[0];
for
(
int
i=1; i<n; i++)
if
(ht < depth[i])
ht = depth[i];
return
ht;
}
Iterative version:
https://gist.github.com/sumitdanish/ec2c7c2fa4306d2bb432
private void height(int[] parent) { | |
int max=Integer.MIN_VALUE; | |
int[] depth = new int[parent.length]; | |
for(int i=0;i<parent.length;i++) | |
{ | |
if(parent[i]==-1) | |
{ | |
depth[i]=1; | |
} | |
else if(depth[parent[i]]==0) | |
{ | |
depth[parent[i]]=1; | |
} | |
else | |
{ | |
depth[i]=depth[parent[i]]+1; | |
} | |
if(max<depth[i]) | |
{ | |
max=depth[i]; | |
} | |
} | |
System.out.println(max); | |
} |
Not efficient:
http://code.geeksforgeeks.org/O8pJpE
public static int getDepth(int arr[])
{
int i = 0;
int j = 0;
int depth = 0;
int maxDepth = 0;
while (i < arr.length)
{
j = i;
depth = 0;
while (j != -1)
{
j = arr[j];
depth++;
}
if (depth > maxDepth)
{
maxDepth = depth;
}
i++;
}
return depth;
}
A simple solution is to first construct the tree and then find height of the constructed binary tree. The tree can be constructed recursively by first searching the current root, then recurring for the found indexes and making them left and right subtrees of root. This solution takes O(n2) as we have to linearly search for every node.
Read full article from Find Height of Binary Tree represented by Parent array - GeeksforGeeks