Given two nodes of a tree, find their most recent common ancestor.

Input. The input consist of one tree. The first line of input is a pair of integers x and y separated by a space. x and y are the nodes that you will consider. The second line of input is a single integer n which is the count of edges in the tree. Each one of the next n lines consist of a pair of integers a and b separated by a space. The pair a b corresponds to an edge from a and b. The following is an example input.

5 7
6
1 2
1 3
3 4
4 5
4 6
6 7

Output. The output consist of a single integer, the most recent common ancestor. The following output corresponds to the example input.

4

Check your solution online

Before you read our solution, try to solve the problem on your own. Remember that practice makes perfect.

Click here to check your solution online at The Book of Problems.

2018-07-09 The Book of Problems currently supports Ruby, Python, Elixir, Java, C, OCaml, and now C++!

Solution

We find the most recent common ancestor in the following way.

We load the graph into a data structure such that there is a reference from each node to its parent. The following diagram illustrates the data structure for the example input.

   1
  / \
 2   3
      \
       4
      / \
     6   5
    /
   7

We place two pebbles A and B on top of the nodes we consider, like so.

   1
  / \
 2   3
      \
       4
      / \
     6   5 A
    /
   7 B

We move the pebble that is farther from the root to the same distance than the other. In our example, we move A from 7 to 6.

   1
  / \
 2   3
      \
       4
      / \
   B 6   5 A
    /
   7

We move both pebbles closer to the root one step at a time until they meet. In our example the pebbles meet at 4.

   1
  / \
 2   3
      \
     B 4 A
      / \
     6   5
    /
   7

The node where the pebbles meet is the most recent common ancestor.

Implementation

Here is a Ruby implementation.

#!/usr/bin/env ruby

def depth n, p
  i = 0
  while !!p[n]
    n = p[n]
    i += 1
  end
  return i
end

def most_recent_common_ancestor a, b, p
  da = depth a, p
  db = depth b, p
  if da < db
    diff = db - da
    while diff > 0
      b = p[b]
      diff -= 1
    end
  elsif db < da
    diff = da - db
    while diff > 0
      a = p[a]
      diff -= 1
    end
  end
  while a != b
    a = p[a]
    b = p[b]
  end
  return a
end

def main
  x, y = readline.strip.split(' ').map(&:to_i)
  n = readline.strip.to_i
  p = {}
  while n > 0
    a, b = readline.strip.split(' ').map(&:to_i)
    p[b] = a
    n -= 1
  end
  puts most_recent_common_ancestor x, y, p
end

main

Want to read more?

I love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments