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 regularly write solutions to programming problems that you may or may not find in technical job interviews. I also love to explain those solutions and 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.