There is a highly optimal O(n) solution available. 1) Find the depth at which each node is situated let them be du and dv respectively for u and v 2) Not bring u and v to the same depth. that is skip abs(du-dv) nodes from the greater depth node 3) Compare both nodes and do a (u=u->parent and v=v->parent) till u and v are not the same. If they are the same you have your common ancestor.
R, Aakash On 3/22/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote: > > > Find the longest common prefix in the path from the root to nodes u and v > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
