# Most Recent Common Ancestor

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.