# First Common Ancestor

Design an algorithm to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in the data structure. Note that this is not necessarily a binary search tree.

#### Solution

The first common ancestor will be the first node for which p is in the left (or right) subtree, and q is in the other subtree. For all parent nodes of the common ancestor, p and q will be in the same child tree. Thus, we can recurse downwards from the root until we reach a node for which p is in one child subtree, and q is in the other child subtree.

First, let’s build a function to identify if a node is contained within a tree. This is fairly straight forward - we can recurse down the tree and return True if the node is identified.

def child(root, node):
if(root == None):
return False
if(root == node):
return True

left_child = child(root.left, node)
right_child = child(root.right, node)

if(left_child or right_child):
return True


Next, let’s build the main function which will also recurse down the tree, until it encounters a node for which p is in one subtree, and q is in the other subtree. If p and q are found in the same subtree, we can recursively call the function on that subtree until p and q are found in different subtrees.

def first_common_ancestor(root, p, q):
if(root == p) or (root == q):
return root

p_left = child(root.left, p)
q_left = child(root.left, q)

if(p_left != q_left):
return root
elif(p_left):
return first_common_ancestor(root.left, p, q)
elif(not p_left):
return first_common_ancestor(root.right, p, q)