Spiral Order Traversal of Binary Tree

Given a binary tree, print its nodes level by level in spiral order. i.e. all nodes present at level 1 should be printed first from left to right, followed by nodes of level 2 right to left, followed by nodes of level 3 from left to right and so on.. In other words, odd levels should be printed from left to right and even levels should be printed from right to left or vice versa.

For example, the level order traversal for below tree is
(1, 3, 2, 4, 5, 6, 7) or (1, 2, 3, 7, 6, 5, 4)

 
binary-tree


 

Simple solution would be to print all nodes of level 1 first, followed by level 2, .. till level h where h is the height of the tree. All nodes present in a level can be printed by modifying pre-order traversal of the tree.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n2).
 
We can reduce time complexity to O(n) by using extra space. Below is pseudocode for a simple queue based spiral order traversal –


levelorder(root)
q -> empty double ended queue
q.push(root)
while (not q.isEmpty())
    while (level is even)
        node -> q.popFront()
        visit(node)
        if (node.left <> null)
            q.pushBack(node.left)
        if (node.right <> null)
            q.pushBack(node.right)

    while (level is odd)
        node -> q.popBack()
        visit(node)
        if (node.right <> null)
            q.pushFront(node.right)
        if (node.left <> null)
            q.pushFront(node.left)

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

We can also solve this problem by using Hashing. Below code traverses the tree in preorder fashion and use map to store every node and its level using level number as a key.

 
C++ implementation –
 

Download   Run Complete Code

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂