# 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) 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 –

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 –

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 –

The time complexity of above solution is O(nlog(n)) and auxiliary space used by the program is O(n).     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂   