problem has many properties like its a BST with parent pointer we shud think of such a solution which uses its both property
If we will think abt the brute force recursive solution its complexity will be O(no_of_nodes*height) which can be made more efficient by putting some restrictions in each recursion sum "s" remaining sum "rs" if node.value > rs/2 then search in left subtree for rs-node.value and s if node.value < rs/2 then search in both subtree for rs-node.value and s stop recursion if rs-node.value ==0 or node.value=s On Sun, Dec 26, 2010 at 10:38 PM, MAC <macatad...@gmail.com> wrote: > you are given a bst where each node has a int value , parent pointer , and > left and right pointers , write a function to find a path with a given sum > value. Path can go from left subtree tree , include root and go to right > tree as well . we need to find these paths also . > > > 5 > 1 10 > 0 2 6 11 > > so to find 16 we say it is 1 to 5 to 10 > > -- > thanks > --mac > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards Aditya Kumar B-tech 3rd year Computer Science & Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
