Spiral Traversal

Spiral Traversal or Zigzag Traversal in a Tree.

This is the fourth article in the Tree Traversals – Online Classes.

Recently I wrote an article on Level Order Tree Traversal. Another problem on the same lines is to traverse the tree in a zigzag manner. That is also termed as spiral traversal. This question has been asked in many companies during the interview process.

Although it is not very specific problem, if you understand the idea behind traversing a tree in breadth first manner, then you can easily solve this. Please read further for more understanding.

Defining the problem

Spiral Traversal
Let us consider the above tree. If we follow the blue line from root till end and print all the nodes, we will end up printing the zigzag/spiral traversal.

So the spiral traversal will print 1, 2, 3, 7, 6, 5, 4, 8, 9, 10, 11, 12, 13, 14, 15.

Approach- Spiral Traversal

As any other tree traversal can be solved either in recursive or iterative way, we can try the same here.

Iterative Way:

For a spiral traversal, we can start from the root and iterate till the height of the tree. Each iteration must print one level of the tree and hence the number of iterations would be equal to the height of the tree. We need to be careful to cautiously swap teh order of printing/visiting every alternate level.

This can be done by using the stack data-structure.
Using Stack

 

Running time of the above algorithm
As we can see there is a nested loop in the first section of the algorithm. The inner loop runs till the stack S1 is not empty and the outer loop also runs for the same amount of time.

In fact the inner loop is just to print one level at a time, which dictates the outer loop to run for O(H) time, where H is the height of the tree.
The inner loop runs for 2K times in each iteration of the outer loop where K is the current level.

The third loop also runs for 2k times in each iteration of the outer loop.

Hence, the running time of the algorithm is O(H) * O(2K) + O(2K) . This means the running time can be translated into
O(2K) (O(H) +1) or can be simply written as O(H) * O(2K)

This means that the running time depends on the height, so if the tree is skewed the running time will seem to increase. The maximum height of the tree can be N and in that case the width of the level would be just one, so the component 2K will reduce to a constant 1. Hence in all cases the running time would be O(2H).

Recursive Way:

I think that the recursive way of traversal is truly not recursive, it eventually relies on iterative steps over the height of the tree and the recursion can only be used in identifying the correct level and printing it.

Why can’t we just use recursion?
A recursion over a node in the tree will either traverse across the height at once and only stops at the leaf. If recursion is used here we end up printing the children before printing the siblings. So each call to recursion must print only one level and the correct one. So, we need three routines, one for printing the current level, which is recursive. The other routine will iterate over the levels and a third one to identify the height of the root.

Routine for iteration

 

Routine for Recursion

Running time of the above algorithm
As we can see the for loop runs for O(H) time where H is the height of the tree. Each of these H calls to the printCurrentLevel routine takes O(H) * O(2K) time as in the previous iterative way and the same justification holds true for this algorithm as well.

Routine for Finding Height of ROOT
You can find this code in one of my previous article “Operations in a binary tree.

Source Code

BinaryNode.java : The data-structure to represent a binary tree node.

Iterative Spiral Traversal Using Stack

Recursive Spiral Traversal

 

Create a sample Tree

Conclusion

Here we learnt different ways of traversing a binary tree in a spiral order. Watch out for more…

Stay connected and stay Subscribed