Lowest common ancestor

Write a program to find the least common ancestor?

The lowest common ancestor (LCA) of two nodes v and w in a tree, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor (Djidjev, Pantziou & Zaroliagis 1991). In ontologies, the lowest common ancestor is also known as the least common ancestor.

// This function returns pointer to LCA of two given 
    // values n1 and n2. 
    // v1 is set as true by this function if n1 is found 
    // v2 is set as true by this function if n2 is found 
    Node findLCAUtil(Node node, int n1, int n2) 
    { 
        // Base case 
        if (node == null) 
            return null; 
          
        //Store result in temp, in case of key match so that we can search for other key also. 
        Node temp=null; 
  
        // If either n1 or n2 matches with root's key, report the presence 
        // by setting v1 or v2 as true and return root (Note that if a key 
        // is ancestor of other, then the ancestor key becomes LCA) 
        if (node.data == n1) 
        { 
            v1 = true; 
            temp = node; 
        } 
        if (node.data == n2) 
        { 
            v2 = true; 
            temp = node; 
        } 
  
        // Look for keys in left and right subtrees 
        Node left_lca = findLCAUtil(node.left, n1, n2); 
        Node right_lca = findLCAUtil(node.right, n1, n2); 
  
        if (temp != null) 
            return temp; 
  
        // If both of the above calls return Non-NULL, then one key 
        // is present in once subtree and other is present in other, 
        // So this node is the LCA 
        if (left_lca != null && right_lca != null) 
            return node; 
  
        // Otherwise check if left subtree or right subtree is LCA 
        return (left_lca != null) ? left_lca : right_lca; 
    } 



Time Complexity: Time complexity of the above solution is O(n).