Finding least Common ancestor in Binary Tree with o(h^2) for a change

Question

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.

Answer 1

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.