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.

leaf nodes in binary search tree

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.

One Thought on “Lowest common ancestor in a Binary Tree.

  1. Hi Everyone,

    Isnt the lowest ancestor for 13 & 14 is supposed to be 8 as 8 is ancestor to 13 and 14 too.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation