Find Height of Binary Tree represented by Parent array | C ++ program to find height using parent array ; This function fills depth of i 'th element in parent[]. The depth is filled in depth[i]. ; If depth [ i ] is already filled ; If node at index i is root ; If depth of parent is not evaluated before , then evaluate depth of parent first ; Depth of this node is depth of parent plus 1 ; This function returns height of binary tree represented by parent array ; 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 ; fill depth of all nodes ; The height of binary tree is maximum of all depths . Find the maximum value in depth [ ] and assign it to ht . ; Driver program to test above functions ; int parent [ ] = { 1 , 5 , 5 , 2 , 2 , - 1 , 3 } ;
#include <bits/stdc++.h> NEW_LINE using namespace std ; void fillDepth ( int parent [ ] , int i , int depth [ ] ) { if ( depth [ i ] ) return ; if ( parent [ i ] == -1 ) { depth [ i ] = 1 ; return ; } if ( depth [ parent [ i ] ] == 0 ) fillDepth ( parent , parent [ i ] , depth ) ; depth [ i ] = depth [ parent [ i ] ] + 1 ; } int findHeight ( int parent [ ] , int n ) { int depth [ n ] ; for ( int i = 0 ; i < n ; i ++ ) depth [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) fillDepth ( parent , i , depth ) ; int ht = depth [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) if ( ht < depth [ i ] ) ht = depth [ i ] ; return ht ; } int main ( ) { int parent [ ] = { -1 , 0 , 0 , 1 , 1 , 3 , 5 } ; int n = sizeof ( parent ) / sizeof ( parent [ 0 ] ) ; cout << " Height ▁ is ▁ " << findHeight ( parent , n ) ; return 0 ; }