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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  100001 NEW_LINE vector < int > tree [ MAXN ] ; int path [ 3 ] [ MAXN ] ; void dfs ( int cur , int prev , int pathNumber , int ptr , int node , bool & flag ) { for ( int i = 0 ; i < tree [ cur ] . size ( ) ; i ++ ) { if ( tree [ cur ] [ i ] != prev and ! flag ) { path [ pathNumber ] [ ptr ] = tree [ cur ] [ i ] ; if ( tree [ cur ] [ i ] == node ) { flag = true ; path [ pathNumber ] [ ptr + 1 ] = -1 ; return ; } dfs ( tree [ cur ] [ i ] , cur , pathNumber , ptr + 1 , node , flag ) ; } } } int LCA ( int a , int b ) { if ( a == b ) return a ; path [ 1 ] [ 0 ] = path [ 2 ] [ 0 ] = 1 ; bool flag = false ; dfs ( 1 , 0 , 1 , 1 , a , flag ) ; flag = false ; dfs ( 1 , 0 , 2 , 1 , b , flag ) ; int i = 0 ; while ( path [ 1 ] [ i ] == path [ 2 ] [ i ] ) i ++ ; return path [ 1 ] [ i - 1 ] ; } void addEdge ( int a , int b ) { tree [ a ] . push_back ( b ) ; tree [ b ] . push_back ( a ) ; } int main ( ) { int n = 8 ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 2 , 6 ) ; addEdge ( 3 , 7 ) ; addEdge ( 3 , 8 ) ; cout << " LCA ( 4 , ▁ 7 ) ▁ = ▁ " << LCA ( 4 , 7 ) << endl ; cout << " LCA ( 4 , ▁ 6 ) ▁ = ▁ " << LCA ( 4 , 6 ) << endl ; return 0 ; }