Find Height of Binary Tree represented by Parent array | This functio 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 reutns 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 Depth of root is 1 ; fill depth of all nodes ; The height of binary tree is maximum of all depths . Find the maximum in depth [ ] and assign it to ht ; int parent [ ] = { 1 , 5 , 5 , 2 , 2 , - 1 , 3 } ;
def fillDepth ( parent , i , depth ) : NEW_LINE INDENT if depth [ i ] != 0 : NEW_LINE INDENT return NEW_LINE DEDENT if parent [ i ] == - 1 : NEW_LINE INDENT depth [ i ] = 1 NEW_LINE return NEW_LINE DEDENT if depth [ parent [ i ] ] == 0 : NEW_LINE INDENT fillDepth ( parent , parent [ i ] , depth ) NEW_LINE DEDENT depth [ i ] = depth [ parent [ i ] ] + 1 NEW_LINE DEDENT def findHeight ( parent ) : NEW_LINE INDENT n = len ( parent ) NEW_LINE depth = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT fillDepth ( parent , i , depth ) NEW_LINE DEDENT ht = depth [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT ht = max ( ht , depth [ i ] ) NEW_LINE DEDENT return ht NEW_LINE DEDENT parent = [ - 1 , 0 , 0 , 1 , 1 , 3 , 5 ] NEW_LINE print " Height ▁ is ▁ % d " % ( findHeight ( parent ) ) NEW_LINE