We could do in O(log n) space and O(nlog n) time complexity. Traverse once to find the maximum depth d ~= log n keeping track of the trail upto root (just as with any recursive traversal). Then traverse d times but visit nodes at depth d, d-1 ... 1 in each traversal. We could optimize the implementation (such as not traversing node below those at the depth we are processing) but the complexity will remain.
If the tree nodes had parent pointer (or sibling pointers) then we can traverse with O(1) space complexity. But asking for such a pointer is by itself asking for O(n) space. On Fri, Oct 2, 2009 at 7:07 AM, Manisha <pgo...@gmail.com> wrote: > > Traversing a binary tree from bottom to top > > The only way I could think of is: > Traverse the binary tree from top to bottom, level by level with the > help of queue. > For a tree like: > a > b c > d e g > The Queue will be something like: > a b c d e g > Now de-queue the element one be one from queue and push on stack. > Pop the stack one by one to get deserved output: > g e d c b a > This will take o(n) space and o(n)time. Is there any better way of > doing it? > > > > > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
