Given two nodes of a tree, find their most recent common ancestor.
The input consist of one tree. The first line of input is a pair of
y separated by a space.
y are the nodes
that you will consider. The second line of input is a single
n which is the count of edges in the tree. Each one of the
n lines consist of a pair of integers
b separated by a
space. The pair
a b corresponds to an edge from
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.
2017-10-08 The Book of Problems currently supports Ruby, Python and now Elixir. More languages will come soon. If there is a language you’d like to use, drop me a line in the comments section.
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
B on top of the nodes we consider, like
We move the pebble that is farther from the root to the same distance
than the other. In our example, we move
We move both pebbles closer to the root one step at a time until they
meet. In our example the pebbles meet at
The node where the pebbles meet is the most recent common ancestor.
Here is a Ruby implementation.
Want to read more?
I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?