I've done this before with a deque although I don't remember the implementation details off my head.
Since a deque allow insertion and removal at both ends what we need to do is decide which end we starting consuming node and which end we add the queues of the next level. For every level we maintain the count of nodes to be processes. Every time this count hits zero we reverse the direction from which we process / add nodes. This is just a simple extension of using queue for doing a BFS traversal. This method would have the same complexity as would BFS using a queue. The above method does not incur any addition overhead. Swamy On Tue, Nov 17, 2009 at 6:35 PM, Nayn <[email protected]> wrote: > Hi guys, > Recently I came across a problem. We've to display a binary tree in > spiral. > 1. We need to print the nodes in BFS manner. > 2. The nodes should be displayed in alternate direction; in one level > from left to right and in next level right to left. > Needless to mention, we need least time complex solution. > Thanks > Nayn > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=. > > > -- 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 [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.
