On Sun, Jan 2, 2011 at 8:30 PM, Akash Agrawal <akash.agrawa...@gmail.com>wrote:
> I have written a kinda messed-up code for the same. Which is basically a > bottom-up approach. > > Please find the same as attached. Some boundary conditions might be missed > and code can be written in a more decorated, beautiful fashion. > > Logic: > > - start from the root, > - keep the nodes value in an array. > - Move up until current node is right child of its parent. > - then search for value in right sub-tree.(LFS) > > > Regards, > Akash Agrawal > http://tech-queries.blogspot.com/ > > > > On Fri, Dec 31, 2010 at 7:59 PM, MAC <macatad...@gmail.com> wrote: > >> No , we had to find all the paths . Some paths could include the root . >> >> >> On Tue, Dec 28, 2010 at 11:12 PM, yq Zhang <zhangyunq...@gmail.com>wrote: >> >>> I think the original question says "Path can go from left subtree tree , >>> include root and go to right tree as well". This should mean the path must >>> include the root. >>> >>> >>> On Tue, Dec 28, 2010 at 4:52 AM, shanushaan < >>> er.srivastavaro...@gmail.com> wrote: >>> >>>> Not clear what path you are referring to. >>>> >>>> Question. Should the path include root value always? (What is problem >>>> with only left or only right path (not containing root)) >>>> In your example for 16 one more path can be 0 1 5 10 as >>>> well. Should algo return all the paths or just first one. >>>> >>>> On Dec 26, 10:08 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. >>>> >>>> >>> -- >>> 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. >>> >> >> >> >> -- >> 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. >> > > -- > 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. > If we rebuild a tree in which a node can point its parent too(adding extra field parent in tree node) then whole tree structure will look like branched linked list. Then, it will be easy to find out the best complexity solution with the help of dynamic programming approach and introducing boundaries. though it will take extra O(n) space and at max O(n^2) time complexity. -- Regards, Rahul Patil -- 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.
