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/divyekapoor
http://www.divye.in
http://gplus.to/divyekapoor
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/Y1yBEXUZC58J.
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.
