Before thinking of writing a function to fulfill it, I try to think of an algorithm. h is denoted to be the maximal distance between the main parent to a given node. It should run in o(h^2) which means it should be easier to come up with such an algorithm, but I constantly find myself with o(h) algorithm. I also get confused when it comes to understanding if I am actually doing a h^2 operation. I could really use a lead.
The simplest algorithm for LCA would run in O(h^2) — make two nested loops, one running over all ancestors of first vertex, the other running over all ancestors of the second, and inside the loop just compare them.
a1 = a // a is the first given vertes
while a1 != nil // assume root's parent is nil
a2 = b // b is the second given vertex
while a2 != nil
if (a1 == a2)
compare with current-best solution
a2 = a2.parent
a1 = a1.parent
So, go up from the first given vertex, that is go through all its ancestors. For each its ancestor a1, go from the second given vertex up to root and check whether you meet the a1 vertex on the way.