if you can access parent in your tree find the path from the nodes to the root then process the two lists from their end and find the last equivalent node in lists and thats the lowest common ancestor the running time is O(height of tree) which is the max length of the two lists
On Thu, Jun 17, 2010 at 2:30 PM, jalaj jaiswal <[email protected]>wrote: > write an algo which gives the lowest common ancestor of two nodes in a > general tree(not binary specifically) > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
