Binary Search Tree : Lowest Common Ancestor

                            Solution in C :

In C++ :




/*
Node is defined as 

typedef struct node
{
   int data;
   node * left;
   node * right;
}node;

*/
bool isPresent(struct node* tree, int k)
{
	if(tree==NULL)
		return false;
	if(tree->data==k)
		return true;
	return isPresent(tree->left,k) || isPresent(tree->right,k);
}


node * lca(node * tree, int m,int n)
{
    
	if(tree==NULL)
		return NULL;
	if(tree->data>m && tree->data>n)
		return lca(tree->left,m,n);
	if(tree->data<m && tree->data<n)
		return lca(tree->right,m,n);
	if(tree->data<m && tree->data>n)
	{
		if(isPresent(tree->left,n) && isPresent(tree->right,m))
		{
			return tree;
		}
		else 
			return NULL;
	}
	if(tree->data>m && tree->data<n)
	{
		if(isPresent(tree->left,m) && isPresent(tree->right,n))
		{
			return tree;
		}
		else 
			return NULL;
	}
	if(tree->data==m)
	{
		if(tree->data<n)
		{
			if(isPresent(tree->right,n))
				return tree;
			else
				return NULL;
		}
		if(tree->data>n)
		{
			if(isPresent(tree->left,n))
				return tree;
			else
				return NULL;
		}
		if(tree->data==n)
			return tree;
	}
	if(tree->data==n)
	{
		if(tree->data<m)
		{
			if(isPresent(tree->right,m))
				return tree;
			else
				return NULL;
		}
		if(tree->data>m)
		{
			if(isPresent(tree->left,m))
				return tree;
			else
				return NULL;
		}
		if(tree->data==m)
			return tree;
	}

    
	return NULL;
	
}


   



In Java :





 /* Node is defined as :
 class Node 
    int data;
    Node left;
    Node right;
    
    */

static Node lca(Node root,int v1,int v2)
    {
        Queue<String> v1path = new LinkedList<String>();
        Queue<String> v2path = new LinkedList<String>();
        String left = "l";
        String right = "r";
        Node rootcopy1 = new Node();
        rootcopy1 = root;
        Node rootcopy2 = new Node();
        rootcopy2 = root;
    
        while(rootcopy1 != null) //finding v1's path
            {
                if(v1 == rootcopy1.data) //found it, no need to continue
                    {
                        break;
                }
                else if(v1 < rootcopy1.data)
                    {
                        v1path.add(left);
                        rootcopy1 = rootcopy1.left;
                }
                else
                    {
                        v1path.add(right);
                        rootcopy1 = rootcopy1.right;
                }
        }
    
        while(rootcopy2 != null) //finding v2's path
            {
                if(v2 == rootcopy2.data) //found it, no need to continue
                    {
                        break;
                }
                else if(v2 < rootcopy2.data)
                    {
                        v2path.add(left);
                        rootcopy2 = rootcopy2.left;
                }
                else
                    {
                        v2path.add(right);
                        rootcopy2 = rootcopy2.right;
                }
        }
    
        rootcopy1 = root; //need to travel along tree down from root again to find LCA to return
    
        while(v1path.peek() != null && v2path.peek() != null) //comparing paths taken to find v1 and v2 to determine LCA
            {
                if(v1path.peek() == v2path.peek()) //if paths take same branch, LCA is farther down from here, keep going
                    {
                        if(v1path.peek() == "l") //take left
                            {
                                v1path.remove();
                                v2path.remove();
                                rootcopy1 = rootcopy1.left;
                        }
                        else //take right
                            {
                                v1path.remove();
                                v2path.remove();
                                rootcopy1 = rootcopy1.right;
                        }
                }
                else //this is the LCA since the paths split here
                    {
                        break;
                }
        }
        return rootcopy1;
    }






In python3 :



# Enter your code here. Read input from STDIN. Print output to STDOUT
'''
class Node:
      def __init__(self,info): 
          self.info = info  
          self.left = None  
          self.right = None 
           

       // this is a node of the tree , which contains info as data, left , right
'''

def lca(root, v1, v2):
    node=root
    if node is None:
        return None
    if node.info>v1 and node.info>v2:
        return lca(node.left,v1,v2)
    elif node.info<v1 and node.info < v2:
        return lca(node.right,v1,v2)
    else:
        return node





In C :




/* you only have to complete the function given below.  
node is defined as  

struct node {
    
    int data;
    struct node *left;
    struct node *right;
  
};

*/
struct node *lca( struct node *root, int v1, int v2 ) {
if( root->data == v1 || root->data == v2 )
            return root;
        if( root->data > v1 && root->data > v2 )
            return lca(root->left, v1, v2);
        if( root->data < v1 && root->data < v2 )
            return lca(root->right, v1, v2);
        return root;
}