How to iterate through a tree in spiral order ???

Question

           1 
      2              3
  4       5        6       7
8  9   10   11   12 13   14  15   

the output in spiral order should be 1 3 2 4 5 6 7 15 14 13 12 11 10 9 8

Answer 1

Think about how you would iterate through the root node and the first level.

Can you write a function for that behavior, and call it recursively?

Answer 2

This is really a variation of a breadth-first search. A breadth-first search uses a queue to get a list of the nodes at the next level down. A queue is a FIFO (first in first out). If you reverse the order at each level you'll get this effect so you need a LIFO (last in first out) instead, otherwise known as a stack.

Answer 3

I know this is a variation of BFS but can any one let me know the exact implementation for the same.