Inward spiral tree traversal

Question

I came across an interesting problem:

Given a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.

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

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

I have thought of a solution:

• Store each level elements in a list
  lists[0] = [1]
  lists[1] = [2, 3]
  lists[2] = [4, 5, 6, 7]
  lists[3] = [8, 9, 10, 11, 12, 13, 14, 15]

• Loop through the list of lists in the order required (0, n-1, 1, n-2, ...) and print. Here n is the number of levels which is 4 in the above case.

Its space complexity would be O(n). I am sure there might be a better solution to it with a better space complexity, but I cannot think if it. Anyone has any pointers?

Answer 1

You don't need to store nodes level by level, you can solve the task by storing all nodes in a deque structure, and also maintaining node's level in an array.

Deque <Integer> deque = new LinkedList();
Queue <Integer> q = new LinkedList();
int[]level = new int[n];//we need to store the level of each node, n is number of node
q.add(0);//Adding the root node
while(!q.isEmpty()){
    int node = q.deque();
    for(int child : getNodeChildren(node)){
         level[child] = level[node] + 1;//Keep track the level of child node
         q.add(child);
         deque.add(child);//Store the child node into the queue.
    }
}
// Print output
boolean printHead = true;
while(!deque.isEmpty()){
   if(printHead){
      int node = deque.pollFirst();
      print node;
      //Check if we already printed every node in this current level, 
      //if yes, we need to switch to print from the end of the queue
      if(!deque.isEmpty() && level[deque.getFirst()] != level[node]){
          printHead = false;
      }
   }else{
      int node = deque.pollLast();
      print node;
      if(!deque.isEmpty() && level[deque.getLast()] != level[node]){
          printHead = true;
      }
   } 
}

The logic of the code is:

We keep printing from the beginning of the deque, if the next node is not in the same level as the last printed node, which also means that we just printed all elements of the current level, we need to switch to print from the end of the deque, vice versa. We continue this process until all nodes are printed.

Space complexity is O(n), time complexity is O(n).