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)
 

level order traversal

 

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(nlog(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 🙂
 






Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Amit
Guest
Amit

Optimized code using D-Q with same logic. https://ideone.com/uVrLQY

yndi
Guest
yndi

Your hashing implementation runs in O(n*log(n)), not in O(n) because std::map uses binary trees under the hood (providing O(log(n)) lookup time complexity) and your input tree can have up to n levels (imagine a degenerate tree). You can still do it in O(n) if you replace map with unordered_map. Unordered maps, however, don’t store their keys in the ordered manner, but you can still iterate it in the desired order because of the recursive function guarantees ensuring your hash map will contain integers from 1 through the tree height.