# 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)
```