Lowest Common Ancestor in a Binary Tree | Set 3 ( Using RMQ ) | CPP code to find LCA of given two nodes in a tree ; the graph ; level of each node ; the segment tree ; adding edges to the graph ( tree ) ; assigning level to nodes ; storing the dfs traversal in the array e ; making the array l ; making the array h ; if is already stored ; Range minimum query to return the index of minimum in the subarray L [ qs : qe ] ; out of range ; in the range ; constructs the segment tree ; leaf ; Function to get LCA ; Driver code ; n = number of nodes in the tree q = number of queries to answer ; 1 / | \ 2 3 4 | \ 5 6 / | \ 8 7 9 ( right of 5 ) / | \ | \ 10 11 12 13 14 | 15
#include <bits/stdc++.h> NEW_LINE #define sz ( x )  x.size() NEW_LINE #define pb  push_back NEW_LINE #define left  2 * i + 1 NEW_LINE #define right  2 * i + 2 NEW_LINE using namespace std ; const int maxn = 100005 ; vector < vector < int > > g ( maxn ) ; int level [ maxn ] ; vector < int > e ; vector < int > l ; int h [ maxn ] ; int st [ 5 * maxn ] ; void add_edge ( int u , int v ) { g [ u ] . pb ( v ) ; g [ v ] . pb ( u ) ; } void leveling ( int src ) { for ( int i = 0 ; i < sz ( g [ src ] ) ; i ++ ) { int des = g [ src ] [ i ] ; if ( ! level [ des ] ) { level [ des ] = level [ src ] + 1 ; leveling ( des ) ; } } } bool visited [ maxn ] ; void dfs ( int src ) { e . pb ( src ) ; visited [ src ] = 1 ; for ( int i = 0 ; i < sz ( g [ src ] ) ; i ++ ) { int des = g [ src ] [ i ] ; if ( ! visited [ des ] ) { dfs ( des ) ; e . pb ( src ) ; } } } void setting_l ( int n ) { for ( int i = 0 ; i < sz ( e ) ; i ++ ) l . pb ( level [ e [ i ] ] ) ; } void setting_h ( int n ) { for ( int i = 0 ; i <= n ; i ++ ) h [ i ] = -1 ; for ( int i = 0 ; i < sz ( e ) ; i ++ ) { if ( h [ e [ i ] ] == -1 ) h [ e [ i ] ] = i ; } } int RMQ ( int ss , int se , int qs , int qe , int i ) { if ( ss > se ) return -1 ; if ( se < qs qe < ss ) return -1 ; if ( qs <= ss && se <= qe ) return st [ i ] ; int mid = ( ss + se ) >> 1 ; int st = RMQ ( ss , mid , qs , qe , left ) ; int en = RMQ ( mid + 1 , se , qs , qe , right ) ; if ( st != -1 && en != -1 ) { if ( l [ st ] < l [ en ] ) return st ; return en ; } else if ( st != -1 ) return st ; else if ( en != -1 ) return en ; } void SegmentTreeConstruction ( int ss , int se , int i ) { if ( ss > se ) return ; if ( ss == se ) { st [ i ] = ss ; return ; } int mid = ( ss + se ) >> 1 ; SegmentTreeConstruction ( ss , mid , left ) ; SegmentTreeConstruction ( mid + 1 , se , right ) ; if ( l [ st [ left ] ] < l [ st [ right ] ] ) st [ i ] = st [ left ] ; else st [ i ] = st [ right ] ; } int LCA ( int x , int y ) { if ( h [ x ] > h [ y ] ) swap ( x , y ) ; return e [ RMQ ( 0 , sz ( l ) - 1 , h [ x ] , h [ y ] , 0 ) ] ; } int main ( ) { ios :: sync_with_stdio ( 0 ) ; int n = 15 , q = 5 ; add_edge ( 1 , 2 ) ; add_edge ( 1 , 3 ) ; add_edge ( 1 , 4 ) ; add_edge ( 3 , 5 ) ; add_edge ( 4 , 6 ) ; add_edge ( 5 , 7 ) ; add_edge ( 5 , 8 ) ; add_edge ( 5 , 9 ) ; add_edge ( 7 , 10 ) ; add_edge ( 7 , 11 ) ; add_edge ( 7 , 12 ) ; add_edge ( 9 , 13 ) ; add_edge ( 9 , 14 ) ; add_edge ( 12 , 15 ) ; level [ 1 ] = 1 ; leveling ( 1 ) ; dfs ( 1 ) ; setting_l ( n ) ; setting_h ( n ) ; SegmentTreeConstruction ( 0 , sz ( l ) - 1 , 0 ) ; cout << LCA ( 10 , 15 ) << endl ; cout << LCA ( 11 , 14 ) << endl ; return 0 ; }