If there are N nodes and it is an n-ary tree, O(N) pre-processing is required for every node, storing its parent in each step.
Subsequently, if LCA(u,v) is to be found, produce the list of ancestors A(u) and A(v), which can be done in O(log-n N) steps. Then compare A(u) and A(v) to find the furthest element in A(u) and A(v) that matches. So O(N) pre-processing and O(log-n N) query time complexity. On Fri, Aug 5, 2011 at 10:22 AM, ankit sambyal <ankitsamb...@gmail.com> wrote: > Find LCA in n ary tree ? > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Gaurav Menghani -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
