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

before thinking of writing function fulfill it, try think of algorithm. h denoted maximal distance between main parent given node. should run in o(h^2) means should easier come such algorithm, find myself o(h) algorithm. confused when comes understanding if doing h^2 operation. use lead.

the simplest algorithm lca run in o(h^2) — make 2 nested loops, 1 running on ancestors of first vertex, other running on ancestors of second, , inside loop compare them.

a1 =  // first given vertes while a1 != nil   // assume root's parent nil     a2 = b  // b second given vertex     while a2 != nil          if (a1 == a2)              compare current-best solution         a2 = a2.parent    a1 = a1.parent 

so, go first given vertex, go through ancestors. each ancestor a1, go second given vertex root , check whether meet a1 vertex on way.