Find LCA in Binary Tree using RMQ | Java program to find LCA of u and v by reducing problem to RMQ ; A binary tree node ; v is the highest value of node in our tree ; for euler tour sequence ; level of nodes in tour sequence ; to store 1 st occurrence of nodes ; variable to fill euler and level arrays ; log base 2 of x ; A recursive function to get the minimum value in a given range of array indexes . The following are parameters for this function . st -- > Pointer to segment tree index -- > Index of current node in the segment tree . Initially 0 is passed as root is always at index 0 ss & se -- > Starting and ending indexes of the segment represented by current node , i . e . , st [ index ] qs & qe -- > Starting and ending indexes of query range ; If segment of this node is a part of given range , then return the min of the segment ; If segment of this node is outside the given range ; If a part of this segment overlaps with the given range ; Return minimum of elements in range from index qs ( query start ) to qe ( query end ) . It mainly uses RMQUtil ( ) ; Check for erroneous input values ; A recursive function that constructs Segment Tree for array [ ss . . se ] . si is index of current node in segment tree st ; If there is one element in array , store it in current node of segment tree and return ; If there are more than one elements , then recur for left and right subtrees and store the minimum of two values in this node ; Function to construct segment tree from given array . This function allocates memory for segment tree and calls constructSTUtil ( ) to fill the allocated memory ; Allocate memory for segment tree Height of segment tree ; Maximum size of segment tree 2 * pow ( 2 , x ) - 1 ; Fill the allocated memory st ; Return the constructed segment tree ; Recursive version of the Euler tour of T ; if the passed node exists ; insert in euler array ; insert l in level array ; increment index ; if unvisited , mark first occurrence ; tour left subtree if exists , and remark euler and level arrays for parent on return ; tour right subtree if exists , and remark euler and level arrays for parent on return ; returns LCA of node n1 and n2 assuming they are present in tree ; Mark all nodes unvisited . Note that the size of firstOccurrence is 1 as node values which vary from 1 to 9 are used as indexes ; To start filling euler and level arrays from index 0 ; Start Euler tour with root node on level 0 ; construct segment tree on level array ; If v before u in Euler tour . For RMQ to work , first parameter ' u ' must be smaller than second ' v ' ; Starting and ending indexes of query range ; query for index of LCA in tour ; return LCA node ; Driver program to test above functions ; Let us create the Binary Tree as shown in the diagram .
import java . util . * ; class Node { Node left , right ; int data ; Node ( int item ) { data = item ; left = right = null ; } } class St_class { int st ; int stt [ ] = new int [ 10000 ] ; } class BinaryTree { Node root ; int v = 9 ; int euler [ ] = new int [ 2 * v - 1 ] ; int level [ ] = new int [ 2 * v - 1 ] ; int f_occur [ ] = new int [ 2 * v - 1 ] ; int fill ; St_class sc = new St_class ( ) ; int Log2 ( int x ) { int ans = 0 ; int y = x >>= 1 ; while ( y -- != 0 ) ans ++ ; return ans ; } int swap ( int a , int b ) { return a ; } int RMQUtil ( int index , int ss , int se , int qs , int qe , St_class st ) { if ( qs <= ss && qe >= se ) return st . stt [ index ] ; else if ( se < qs ss > qe ) return - 1 ; int mid = ( ss + se ) / 2 ; int q1 = RMQUtil ( 2 * index + 1 , ss , mid , qs , qe , st ) ; int q2 = RMQUtil ( 2 * index + 2 , mid + 1 , se , qs , qe , st ) ; if ( q1 == - 1 ) return q2 ; else if ( q2 == - 1 ) return q1 ; return ( level [ q1 ] < level [ q2 ] ) ? q1 : q2 ; } int RMQ ( St_class st , int n , int qs , int qe ) { if ( qs < 0 qe > n - 1 qs > qe ) { System . out . println ( " Invalid ▁ input " ) ; return - 1 ; } return RMQUtil ( 0 , 0 , n - 1 , qs , qe , st ) ; } void constructSTUtil ( int si , int ss , int se , int arr [ ] , St_class st ) { if ( ss == se ) st . stt [ si ] = ss ; else { int mid = ( ss + se ) / 2 ; constructSTUtil ( si * 2 + 1 , ss , mid , arr , st ) ; constructSTUtil ( si * 2 + 2 , mid + 1 , se , arr , st ) ; if ( arr [ st . stt [ 2 * si + 1 ] ] < arr [ st . stt [ 2 * si + 2 ] ] ) st . stt [ si ] = st . stt [ 2 * si + 1 ] ; else st . stt [ si ] = st . stt [ 2 * si + 2 ] ; } } int constructST ( int arr [ ] , int n ) { int x = Log2 ( n ) + 1 ; int max_size = 2 * ( 1 << x ) - 1 ; sc . stt = new int [ max_size ] ; constructSTUtil ( 0 , 0 , n - 1 , arr , sc ) ; return sc . st ; } void eulerTour ( Node node , int l ) { if ( node != null ) { euler [ fill ] = node . data ; level [ fill ] = l ; fill ++ ; if ( f_occur [ node . data ] == - 1 ) f_occur [ node . data ] = fill - 1 ; if ( node . left != null ) { eulerTour ( node . left , l + 1 ) ; euler [ fill ] = node . data ; level [ fill ] = l ; fill ++ ; } if ( node . right != null ) { eulerTour ( node . right , l + 1 ) ; euler [ fill ] = node . data ; level [ fill ] = l ; fill ++ ; } } } int findLCA ( Node node , int u , int v ) { Arrays . fill ( f_occur , - 1 ) ; fill = 0 ; eulerTour ( root , 0 ) ; sc . st = constructST ( level , 2 * v - 1 ) ; if ( f_occur [ u ] > f_occur [ v ] ) u = swap ( u , u = v ) ; int qs = f_occur [ u ] ; int qe = f_occur [ v ] ; int index = RMQ ( sc , 2 * v - 1 , qs , qe ) ; return euler [ index ] ; } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 2 ) ; tree . root . right = new Node ( 3 ) ; tree . root . left . left = new Node ( 4 ) ; tree . root . left . right = new Node ( 5 ) ; tree . root . right . left = new Node ( 6 ) ; tree . root . right . right = new Node ( 7 ) ; tree . root . left . right . left = new Node ( 8 ) ; tree . root . left . right . right = new Node ( 9 ) ; int u = 4 , v = 9 ; System . out . println ( " The ▁ LCA ▁ of ▁ node ▁ " + u + " ▁ and ▁ " + v + " ▁ is ▁ " + tree . findLCA ( tree . root , u , v ) ) ; } }