LCA for general or n | Program to find LCA of n1 and n2 using one DFS on the Tree ; 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
import java . util . * ; class GFG { static final int MAXN = 100001 ; static Vector < Integer > [ ] tree = new Vector [ MAXN ] ; static int [ ] [ ] path = new int [ 3 ] [ MAXN ] ; static boolean flag ; static void dfs ( int cur , int prev , int pathNumber , int ptr , int node ) { for ( int i = 0 ; i < tree [ cur ] . size ( ) ; i ++ ) { if ( tree [ cur ] . get ( i ) != prev && ! flag ) { path [ pathNumber ] [ ptr ] = tree [ cur ] . get ( i ) ; if ( tree [ cur ] . get ( i ) == node ) { flag = true ; path [ pathNumber ] [ ptr + 1 ] = - 1 ; return ; } dfs ( tree [ cur ] . get ( i ) , cur , pathNumber , ptr + 1 , node ) ; } } } static int LCA ( int a , int b ) { if ( a == b ) return a ; path [ 1 ] [ 0 ] = path [ 2 ] [ 0 ] = 1 ; flag = false ; dfs ( 1 , 0 , 1 , 1 , a ) ; flag = false ; dfs ( 1 , 0 , 2 , 1 , b ) ; int i = 0 ; while ( i < MAXN && path [ 1 ] [ i ] == path [ 2 ] [ i ] ) i ++ ; return path [ 1 ] [ i - 1 ] ; } static void addEdge ( int a , int b ) { tree [ a ] . add ( b ) ; tree [ b ] . add ( a ) ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < MAXN ; i ++ ) tree [ i ] = new Vector < Integer > ( ) ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 2 , 6 ) ; addEdge ( 3 , 7 ) ; addEdge ( 3 , 8 ) ; System . out . print ( " LCA ( 4 , ▁ 7 ) ▁ = ▁ " + LCA ( 4 , 7 ) + "NEW_LINE"); System . out . print ( " LCA ( 4 , ▁ 6 ) ▁ = ▁ " + LCA ( 4 , 6 ) + "NEW_LINE"); } }