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.

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

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

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.

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

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.

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

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

# Implementation

Here is a Ruby implementation.

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.