Lowest Common Ancestor in Parent Array Representation | Maximum value in a node ; Function to find the Lowest common ancestor ; Create a visited vector and mark all nodes as not visited . ; Moving from n1 node till root and mark every accessed node as visited ; Move to the parent of node n1 ; For second node finding the first node common ; Insert function for Binary tree ; Driver Code ; Maximum capacity of binary tree ; Root marked
MAX = 1000 NEW_LINE def findLCA ( n1 , n2 , parent ) : NEW_LINE INDENT visited = [ False for i in range ( MAX ) ] NEW_LINE visited [ n1 ] = True NEW_LINE while ( parent [ n1 ] != - 1 ) : NEW_LINE INDENT visited [ n1 ] = True NEW_LINE n1 = parent [ n1 ] NEW_LINE DEDENT visited [ n1 ] = True NEW_LINE while ( visited [ n2 ] == False ) : NEW_LINE INDENT n2 = parent [ n2 ] NEW_LINE DEDENT return n2 NEW_LINE DEDENT def insertAdj ( parent , i , j ) : NEW_LINE INDENT parent [ i ] = j NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT parent = [ 0 for i in range ( MAX ) ] NEW_LINE parent [ 20 ] = - 1 NEW_LINE insertAdj ( parent , 8 , 20 ) NEW_LINE insertAdj ( parent , 22 , 20 ) NEW_LINE insertAdj ( parent , 4 , 8 ) NEW_LINE insertAdj ( parent , 12 , 8 ) NEW_LINE insertAdj ( parent , 10 , 12 ) NEW_LINE insertAdj ( parent , 14 , 12 ) NEW_LINE print ( findLCA ( 10 , 14 , parent ) ) NEW_LINE DEDENT