CareerCup

This problem reduces to finding the point of intersection of two linked lists (because parent pointers are given).

node* LCA(node *x,node *y)
{
    int d1=0,d2=0;
    for(node *i=x;i!=NULL;i=i->parent) d1++;
    for(node *i=y;i!=NULL;i=i->parent) d2++;

    if(d1!=d2)
    {
        while(d1<d2) {
            y=y->parent;
            d2--;
        }
        while(d1>d2) {
            x=x->parent;
            d1--;
        }
    }
    while(x!=y)
    {
        x=x->parent;
        y=y->parent;
    }
    return x;
}

ttp://geeksforgeeks.org/?p=1029

The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side.

Implementation:
view source
print?
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;

/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;

if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}
/* Driver program to test mirror() */
int main()
{
struct node *root = newNode(2);
root->left = newNode(1);
root->right = newNode(4);
root->right->left = newNode(3);
root->right->right = newNode(5);

/* Constructed binary search tree is
2
/ \
1 4
/ \
3 5
*/
printf("\n The Least Common Ancestor is \n");
printf("%d", leastCommanAncestor(root, 3, 5));

getchar();
return 0;
}

Here is a generic solution for finding LCA for two values in a general binary tree. Now for BST, we can do some simple trimming of the recursion so it will be fast. Leave to you to think:

// find least common ancestor in a binary treeu.
int max_level = -1;
int lca_value = 0;
// node: current node.
// a, b: two values we're looking their LCA for. they don't need to
//       to be ordered, that a not necessarily smaller than b.
// pa, pb: returns to call that whether value a and/or value b exists
//         in this sub tree with node as its root.
// level: how deep are we in the tree.
// assumption the all the values in the tree are unique.
void FindLca(NODE *node, int a, int b, bool *pa, bool *pb, int level)
{
    *pa = *pb = false;

    if (!node) goto exit;

    if (node->value == a) { *pa = true; }
    if (node->value == b) { *pb = true; }

    bool la = false, ra = false, lb = false, rb = false;

    if (node->left)
    {
        FindLca(node->left, a, b, &la, &lb, level + 1);
    }
    if (node->right)
    {
        FindLca(node->right, a, b, &ra, &rb, level + 1);
    }

    if (!*pa) { *pa = la || ra; }
    if (!*pb) { *pb = lb || rb; }

exit: 

    if (*pa && *pb && level > max_level)
    {
        max_level = level;
        lca_value = node->value;
    }
}

Here is a simpler solution. As you find parent keep on inserting in a hash table. Look for other nodes parent in hash table. First point where its found is LCA.

Node* LCA(Node* root, Node* x, Node* y) { 
   if(x == root || y == root || x == NULL || y == NULL) { return NULL; }
   hash_set<Node*> parents;
   while(x->parent) { 
      parents.insert(x->parent);
      x = x->parent;
   }

  while(y->parent) { 
     if(parents.find(y->parent) != parents.end()) { return y->parent; } 
     y = y->parent;
  }

  return NULL;
}

Start with one node and while navigate towards root, put the node into a hashtable.
Do the same for the second node but verify if the node is in the hashtable.

Find the depth of both nodes. Lets say depth of node X be 15 & node Y be 10. Then traverse node X (larger depth) towards parent by 5 (15-10) nodes. Lets say it comes out to be Z.
After this traverse both Z & Y towards parent node & keep on matching them. First common match is a LCA.

Same as two linked list which are having common node

Its easier than mentioned in the answers above. Find the shorted depth, let's call it s. Traverse the node with higher depth up s times to its parent and you are done !

What if traversing the larger depth node up 5 times(if 5 is the diff between the depth of two nodes) takes you past the LCA of the two nodes .... ??? IN this case the aboce solution wont work...

Let us have two stacks S1 and S2. Let a and b be the two nodes for which LCA have to be found. Move up from 'a' and store the way(nodes) in S1. Move up from 'b' and store the way in S2.Now pop the stacks until a mismatch occurs or one of the path ends. The node before the first mismatch or the the last node before one of the stacks become empty is the LCA.

This code should do the trick :
1 traversal until encounter the first node;
2 check if second node is under the first node, if so, the first node self is LCA, otherwise ,go3
3. go back with parent pointer until found one which have right subtree and the second node is in it , then this node is LCA.

Node *	LCA(Node *root, Node *n1, Node *n2)
{
	bool find = false;  // keep track of if lca is found or not
	Node *lca = NULL;
	DoLCA(root, n1, n2, find, lca);
	Return lca;
}

Void 	DoLCA(Node *root, Node *n1, Node *n2, bool &find, Node *&lca)
{
	if ( root == NULL)
		Return ;

	// encounter the first node
	If ( root == n1 || root == n2)
	{
		Node *Second = root == n1 ? n2 : n1;
		If (Cover(root, second))
			Lca = root;
		Else
		{
			While(root)
			{
				root = root->parenet;
				If(root->Right && Cover(root->Right, second))
				{
					Lca = root;
					Break;
				}
			}
		}
		Find = true;
		Return;
	}
	
	// go left
	DoLCA(root->Left, n1, n2, second, flag, lca);
	If (find)
		Return;    // lca found , just return, no need to go right 
	// go right
	DoLCA(root->Left, n1, n2, second, flag, lca);
}

This code should do the trick :
1 traversal until encounter the first node;
2 check if second node is under the first node, if so, the first node self is LCA, otherwise ,go3
3. go back with parent pointer until found one which have right subtree and the second node is in it , then this node is LCA.

Node *	LCA(Node *root, Node *n1, Node *n2)
{
	bool find = false;  // keep track of if lca is found or not
	Node *lca = NULL;
	DoLCA(root, n1, n2, find, lca);
	Return lca;
}

Void 	DoLCA(Node *root, Node *n1, Node *n2, bool &find, Node *&lca)
{
	if ( root == NULL)
		Return ;

	// encounter the first node
	If ( root == n1 || root == n2)
	{
		Node *Second = root == n1 ? n2 : n1;
		If (Cover(root, second))
			Lca = root;
		Else
		{
			While(root)
			{
				root = root->parenet;
				If(root->Right && Cover(root->Right, second))
				{
					Lca = root;
					Break;
				}
			}
		}
		Find = true;
		Return;
	}
	
	// go left
	DoLCA(root->Left, n1, n2, second, flag, lca);
	If (find)
		Return;    // lca found , just return, no need to go right 
	// go right
	DoLCA(root->Left, n1, n2, second, flag, lca);
}

@all:simpler approach is to find the depth of x and y from top......then
pseudocode:
{while(p[x]!=p[y])
{
if(depth[x]>depth[y])x=p[x];
else
y=p[y];
}
return x;
if any mistake then crct me.....

@all:simpler approach is to find the depth of x and y from top......then
pseudocode:
{while(p[x]!=p[y])
{
if(depth[x]>depth[y])x=p[x];
else
y=p[y];
}
return x;
if any mistake then crct me.....

LCA is a binary search tree (BST) is simple. For any nodes x and y, the LCA is the first node which lies between x and y starting from root.


Node getLCA_BST(Node root, Node x, Node y):
Node curr = root
while !(x < curr && curr < y): // x.value < curr.value
if curr < x && curr < y:
curr = curr.right
else: //x < curr && y < curr
curr = curr.left
return curr // assume x and y are in the tree