Any help regarding the preprocessing required for O(1) operation for LCA??? I read the wiki's article involving eulers traversal.. but its nt clear.
On Aug 24, 1:12 am, DK <divyekap...@gmail.com> wrote: > Hmm.. Interesting question. > > *Here's a solution:* > > There are n elements in the tree and therefore n^2 paths in the tree > (duplicate endpoints allowed and 2 endpoints correspond to exactly 1 simple > path in the tree). > 1. For each node in the BST, store the sum of node values on the path to the > root. Can be done using a simple DFS in O(N). > Also perform preprocessing for the LCA function (required below). > > 2. For each pair of nodes (u, v) in the BST: - O(N^2) > Cost of path = Cost(u, root) + Cost(v, root) - Cost(LCA(u,v), root) > If(Cost of path == value) print_path(u,v) > > The LCA is the lowest common ancestor of the given nodes > (See:http://en.wikipedia.org/wiki/Lowest_common_ancestor) > LCA(u,v) is an O(1) operation given O(N) preprocessing of the tree. > > Therefore, we know for sure that we can do this problem in worst case > O(N^2). > > *Optimizations: *I'm not sure any of these yield worst case bound > improvements but here are a few things that you can do: > 1. Get rid of symmetry: (u, v) is the same as (v, u). Choose u < v always. > 2. For a chosen u, skip all children of v if target cost > v > > Time Complexity: O(N^2) > Space Complexity: O(N) > > -- > DK > > http://twitter.com/divyekapoorhttp://www.divye.inhttp://gplus.to/divyekapoor -- 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.
