It depends on the tree structure. If we have root of the tree, this can be done in O(height) time. However, if there is many queries of such type, the preprocession should be applied. Refer to the TopCoder tutorial about LCA: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
-- 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.
