Finding the common ancestor in a binary tree

Question

This question was asked to me in an interview: I have a binary tree and I have to find the common ancestor (parent) given two random nodes of that tree. I am also given a pointer to the root node.

---

My answer is:

Traverse the tree separately for both the nodes till you reach the node that is expected. Parallel while traversing store the element and the next address in a linked list. Then we have two linked lists with us. So try comparing the two linked lists and the last common node in both the linked lists is the parent.

I am thinking that this solution is correct, correct me if I am wrong. If this solution is correct, may I know is this the only better solution for this task or is there any other better solution than this!

Answer 1

Maybe silly approach:

Generate the path from each node to the root, storing it as a string of "L" and "R".

Reverse these strings. Take the longest common prefix - you now have the path to the common ancestor.

Answer 2

Set a pointer at both of the random nodes. Find the depth of each node by traversing to the top and counting the distance from the root node. Then set the pointer at both nodes again. For the deeper node, traverse up until both pointers are at the same depth. Then traverse up for both nodes until the pointers point to the same node. That is the ancestor node.

By "traverse up" I just mean move the pointer to the parent of the current node.

Edit to clarify: The key idea is that when both nodes are at the same depth, you can find the common parent very quickly just by simple traversal. So you climb the lower one until both are at the same depth, and then you traverse up. Sorry I don't really know C or I'd write code, but that algorithm should answer your question.

Edit again: And my method runs in O(log(n)) time and O(1) memory.

Another edit: O(log(n)) in a balanced tree. Worst-case performance is O(n) for an unbalanced tree. Thanks @DaveCahill

Answer 3

I think you could just do a search simultaneously for both nodes; the point at which the search diverges is the common ancestor.

commonAncestor tree a b:
  value := <value of node 'tree'>
  if (a < value) && (b < value)
  then commonAncestor (left tree) a b
  else if (a > value) && (b > value)
  then commonAncestor (right tree) a b
  else tree

Interestingly this approach would scale to more than two nodes (check for all of them to be on the left side of tree, etc.)

Answer 4

Make a level order traversal, and for each node we encounter we check its children. If they are the provided random nodes, then the ancestor node is found.

EDIT1:

Here is an outline

struct _node {
   my_type data;
   struct _node *left;
   struct _node *right;
}

q = queue_create ();
queue_insert (q, head);
temp = head;
while (!empty (q))
{
    temp = queue_remove (q);
 if (
      (temp->left == my_random_node_1) && (head->right == my_random_node_2) ||
      (temp->left == my_random_node_2) && (head->right == my_random_node_1)
    )
    {
       /* temp is the common parent of the two target notes */
       /* Do stuffs you need to do */
    }

    /* Enqueue the childs, so that in successive iterations we can
     * check them, by taking out from the queue
     */
    push (q, temp->left);
    push (q, temp->right);
}

---

UPDATE

The previous algorithm will only find common parents (direct ancestor), therefore if two randomly selected nodes if are not a child of common parent no answer would be found.

The below algorithm will find common ancestors and not only parents.

I think the following algorithm will work:

Make a postorder traversal of the binary tree, and find for the random node 1 r1, if we find it then mark it in a state variable to be in state one, and keep finding for the second node, if found then update the state variable to state two, and stop searching more and return. The state variable should be passed by every node to its parents (recursively). The first node which encounters the state variable in state two is the common ancestor.

The implementation of the algorithm is as follows:

int postorder (node *p, int r1, int r2)
{
  int x = 0; /* The state variable */
  if (p->data == TERMINAL_VAL)
    return x;

  /* 0x01 | 0x02 = 0x03 threfore 
   * state one is when x = 0x01 or x = 0x02
   * state two is when x = 0x03
   */
  if (p->data == r1)
    x |= 0x01;
  else if (p->data == r2)
    x |= 0x02;

  /* if we have x in state two, no need to search more
   */
  if (x != 0x03)
    x |= postorder (p->left, r1, r2);
  if (x != 0x03)
    x |= postorder (p->right, r1, r2);

  /* In this node we are in state two, print node if this node
   * is not any of the two nodes r1 and r2. This makes sure that
   * is one random node is an ancestor of another random node
   * then it will not be printed instead its parent will be printed
   */
  if ((x == 0x03) && (p->data != r1) && (p->data != r2))
  {
   printf ("[%c] ", p->data);
   /* set state variable to 0 if we do not want to print 
    * the ancestors of the first ancestor 
    */
   x = 0;
  }

  /* return state variable to parent
   */    
  return x;
}

I think this will work correctly, though i am still to prove the algorithm's correctness. There is one drawback, which is, if one node is a child of another node, then it will print only the node which is the parent of the other one, instead of printing the parent of them. If one of the random node is an ancestor of another random node then instead of printing the ancestor random node, it will print the parent of it. In the case in which one of the random node is the root node, it will print nothing, as it is always the ancestor of the other random node, and therefore their common ancestor does not exist. In this special case the function will return 0x03 in main and it can be detected.

As this algorithm does a postorder traversal therefore it requires O(n) execution time and thus O(n) memory. Also as the search stops as soon both the nodes are found, the shallower the nodes the quicker the search ends.

UPDATE

Here are some mode discussions: How to find the lowest common ancestor of two nodes in any binary tree?

Answer 5

This problem has been very well-studied and there are known algorithms that can solve it in linear time. This paper describes many different approaches you can use to solve it. Admittedtly it is a research paper and so the algorithms are a bit tricky, but some of the approaches it describes are actually quite feasible.