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.

# 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.

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.

# 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.