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.
5 7
6
1 2
1 3
3 4
4 5
4 6
6 7
Output. The output consist of a single integer, the most recent common ancestor. The following output corresponds to the example input.
4
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.
1
/ \
2 3
\
4
/ \
6 5
/
7
We place two pebbles A
and B
on top of the nodes we consider, like
so.
1
/ \
2 3
\
4
/ \
6 5 A
/
7 B
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
.
1
/ \
2 3
\
4
/ \
B 6 5 A
/
7
We move both pebbles closer to the root one step at a time until they
meet. In our example the pebbles meet at 4
.
1
/ \
2 3
\
B 4 A
/ \
6 5
/
7
The node where the pebbles meet is the most recent common ancestor.
Implementation
Here is a Ruby implementation.
#!/usr/bin/env ruby
def depth n, p
i = 0
while !!p[n]
n = p[n]
i += 1
end
return i
end
def most_recent_common_ancestor a, b, p
da = depth a, p
db = depth b, p
if da < db
diff = db - da
while diff > 0
b = p[b]
diff -= 1
end
elsif db < da
diff = da - db
while diff > 0
a = p[a]
diff -= 1
end
end
while a != b
a = p[a]
b = p[b]
end
return a
end
def main
x, y = readline.strip.split(' ').map(&:to_i)
n = readline.strip.to_i
p = {}
while n > 0
a, b = readline.strip.split(' ').map(&:to_i)
p[b] = a
n -= 1
end
puts most_recent_common_ancestor x, y, p
end
main
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.