Lowest common ancestor in a Binary Tree.

Problem : Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

Lowest Common Ancestor: The lowest common ancestor (LCA) of two nodes v and w is defined as the lowest node in tree that has both v and w as descendants (where we allow a node to be a descendant of itself). The LCA of v and w in tree is the shared ancestor of v and w that is located farthest from the root.

In above binary tree, LCA of 1 and 7 is 3.

LCA of 6 and 10 is 8.

LCA of 14 and 13 is 14.

struct node* LCA(struct node* root, struct node* p, struct node *q)
{
	struct node *l,*r,*temp;
	
	if (root == NULL)
		return NULL;
	if (root == p || root == q)
		return root;
		
	L = LCA(root->left, p, q);
	R = LCA(root->right, p, q);
	
	if (L && R) //if both nodes on either side of tree.
		return root;
	return L ? L : R;  // either both nodes are on same side or not in left and right subtree.
}

Explanation: We traverse from the bottom, and when we reach a node which matches one of two nodes, we pass it up to it’s parent,parent would check it’s left and right subtree,if each contains one of two nodes,if yes, then parent is the LCA and we pass it to it’s parent up to the root.if not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Time Complexity: O(log(n)) in Balanced binary tree, O(n) in skewed tree.