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)