LCA for general or n | Maximum number of nodes is 100000 and nodes are numbered from 1 to 100000 ; Storing root to node path ; Storing the path from root to node ; Pushing current node into the path ; Node found ; Terminating the path ; This Function compares the path from root to ' a ' & root to ' b ' and returns LCA of a and b . Time Complexity : O ( n ) ; Trivial case ; Setting root to be first element in path ; Calculating path from root to a ; Calculating path from root to b ; Runs till path 1 & path 2 mathches ; Returns the last matching node in the paths ; Driver code ; Number of nodes
MAXN = 100001 NEW_LINE tree = [ 0 ] * MAXN NEW_LINE for i in range ( MAXN ) : NEW_LINE INDENT tree [ i ] = [ ] NEW_LINE DEDENT path = [ 0 ] * 3 NEW_LINE for i in range ( 3 ) : NEW_LINE INDENT path [ i ] = [ 0 ] * MAXN NEW_LINE DEDENT flag = False NEW_LINE def dfs ( cur : int , prev : int , pathNumber : int , ptr : int , node : int ) -> None : NEW_LINE INDENT global tree , path , flag NEW_LINE for i in range ( len ( tree [ cur ] ) ) : NEW_LINE INDENT if ( tree [ cur ] [ i ] != prev and not flag ) : NEW_LINE INDENT path [ pathNumber ] [ ptr ] = tree [ cur ] [ i ] NEW_LINE if ( tree [ cur ] [ i ] == node ) : NEW_LINE INDENT flag = True NEW_LINE path [ pathNumber ] [ ptr + 1 ] = - 1 NEW_LINE return NEW_LINE DEDENT dfs ( tree [ cur ] [ i ] , cur , pathNumber , ptr + 1 , node ) NEW_LINE DEDENT DEDENT DEDENT def LCA ( a : int , b : int ) -> int : NEW_LINE INDENT global flag NEW_LINE if ( a == b ) : NEW_LINE INDENT return a NEW_LINE DEDENT path [ 1 ] [ 0 ] = path [ 2 ] [ 0 ] = 1 NEW_LINE flag = False NEW_LINE dfs ( 1 , 0 , 1 , 1 , a ) NEW_LINE flag = False NEW_LINE dfs ( 1 , 0 , 2 , 1 , b ) NEW_LINE i = 0 NEW_LINE while ( path [ 1 ] [ i ] == path [ 2 ] [ i ] ) : NEW_LINE INDENT i += 1 NEW_LINE DEDENT return path [ 1 ] [ i - 1 ] NEW_LINE DEDENT def addEdge ( a : int , b : int ) -> None : NEW_LINE INDENT tree [ a ] . append ( b ) NEW_LINE tree [ b ] . append ( a ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 8 NEW_LINE addEdge ( 1 , 2 ) NEW_LINE addEdge ( 1 , 3 ) NEW_LINE addEdge ( 2 , 4 ) NEW_LINE addEdge ( 2 , 5 ) NEW_LINE addEdge ( 2 , 6 ) NEW_LINE addEdge ( 3 , 7 ) NEW_LINE addEdge ( 3 , 8 ) NEW_LINE print ( " LCA ( 4 , ▁ 7 ) ▁ = ▁ { } " . format ( LCA ( 4 , 7 ) ) ) NEW_LINE print ( " LCA ( 4 , ▁ 6 ) ▁ = ▁ { } " . format ( LCA ( 4 , 6 ) ) ) NEW_LINE DEDENT