Program to find LCA of u and v by reducing the problem to RMQ

/* C++ Program to find LCA of u and v by reducing the problem to RMQ */
#include<bits/stdc++.h> 
#define V 9               // number of nodes in input tree 

  

int euler[2*V - 1];       // For Euler tour sequence 

int level[2*V - 1];       // Level of nodes in tour sequence 

int firstOccurrence[V+1]; // First occurrences of nodes in tour 

int ind;                  // Variable to fill-in euler and level arrays 

  
// A Binary Tree node 

struct Node 
{ 

    int key; 

    struct Node *left, *right; 
}; 

  
// Utility function creates a new binary tree node with given key 

Node * newNode(int k) 
{ 

    Node *temp = new Node; 

    temp->key = k; 

    temp->left = temp->right = NULL; 

    return temp; 
} 

  
// log base 2 of x 

int Log2(int x) 
{ 

    int ans = 0 ; 

    while (x>>=1) ans++; 

    return ans ; 
} 

  
/*  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 */

int RMQUtil(int index, int ss, int se, int qs, int qe, int *st) 
{ 

    // If segment of this node is a part of given range, then return 

    //  the min of the segment 

    if (qs <= ss && qe >= se) 

        return st[index]; 

  

    // If segment of this node is outside the given range 

    else if (se < qs || ss > qe) 

        return -1; 

  

    // If a part of this segment overlaps with the given range 

    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; 
} 

  
// Return minimum of elements in range from index qs (query start) to 
// qe (query end).  It mainly uses RMQUtil() 

int RMQ(int *st, int n, int qs, int qe) 
{ 

    // Check for erroneous input values 

    if (qs < 0 || qe > n-1 || qs > qe) 

    { 

        printf("Invalid Input"); 

        return -1; 

    } 

  

    return RMQUtil(0, 0, n-1, qs, qe, st); 
} 

  
// A recursive function that constructs Segment Tree for array[ss..se]. 
// si is index of current node in segment tree st 

void constructSTUtil(int si, int ss, int se, int arr[], int *st) 
{ 

    // If there is one element in array, store it in current node of 

    // segment tree and return 

    if (ss == se)st[si] = ss; 

  

    else

    { 

        // If there are more than one elements, then recur for left and 

        // right subtrees and store the minimum of two values in this node 

        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[2*si+1]] < arr[st[2*si+2]]) 

            st[si] = st[2*si+1]; 

        else

            st[si] = st[2*si+2]; 

    } 
} 

  
/* Function to construct segment tree from given array. This function 

   allocates memory for segment tree and calls constructSTUtil() to 

   fill the allocated memory */

int *constructST(int arr[], int n) 
{ 

    // Allocate memory for segment tree 

  

    // Height of segment tree 

    int x = Log2(n)+1; 

  

    // Maximum size of segment tree 

    int max_size = 2*(1<<x) - 1;  //  2*pow(2,x) -1 

  

    int *st = new int[max_size]; 

  

    // Fill the allocated memory st 

    constructSTUtil(0, 0, n-1, arr, st); 

  

    // Return the constructed segment tree 

    return st; 
} 

  
// Recursive version of the Euler tour of T 

void eulerTour(Node *root, int l) 
{ 

    /* if the passed node exists */

    if (root) 

    { 

        euler[ind] = root->key; // insert in euler array 

        level[ind] = l;         // insert l in level array 

        ind++;                  // increment index 

  

        /* if unvisited, mark first occurrence */

        if (firstOccurrence[root->key] == -1) 

            firstOccurrence[root->key] = ind-1; 

  

        /* tour left subtree if exists, and remark euler 

           and level arrays for parent on return */

        if (root->left) 

        { 

            eulerTour(root->left, l+1); 

            euler[ind]=root->key; 

            level[ind] = l; 

            ind++; 

        } 

  

        /* tour right subtree if exists, and remark euler 

           and level arrays for parent on return */

        if (root->right) 

        { 

            eulerTour(root->right, l+1); 

            euler[ind]=root->key; 

            level[ind] = l; 

            ind++; 

        } 

    } 
} 

  
// Returns LCA of nodes n1, n2 (assuming they are 
//  present in the tree) 

int findLCA(Node *root, int u, int v) 
{ 

    /* 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 */

    memset(firstOccurrence, -1, sizeof(int)*(V+1)); 

  

    /* To start filling euler and level arrays from index 0 */

    ind = 0; 

  

    /* Start Euler tour with root node on level 0 */

    eulerTour(root, 0); 

  

    /* construct segment tree on level array */

    int *st = constructST(level, 2*V-1); 

  

    /* If v before u in Euler tour.  For RMQ to work, first 

       parameter 'u' must be smaller than second 'v' */

    if (firstOccurrence[u]>firstOccurrence[v]) 

       std::swap(u, v); 

  

    // Starting and ending indexes of query range 

    int qs = firstOccurrence[u]; 

    int qe = firstOccurrence[v]; 

  

    // query for index of LCA in tour 

    int index = RMQ(st, 2*V-1, qs, qe); 

  

    /* return LCA node */

    return euler[index]; 
} 

  
// Driver program to test above functions 

int main() 
{ 

    // Let us create the Binary Tree as shown in the diagram. 

    Node * root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

    root->left->left = newNode(4); 

    root->left->right = newNode(5); 

    root->right->left = newNode(6); 

    root->right->right = newNode(7); 

    root->left->right->left = newNode(8); 

    root->left->right->right = newNode(9); 

  

    int u = 4, v = 9; 

    printf("The LCA of node %d and node %d is node %d.\n",  

            u, v, findLCA(root, u, v)); 

    return 0; 
}