This is also called zig-zag order traversal of a binary tree.
Approach: To print the nodes in spiral order, nodes at different levels should be printed in alternating order. To change the order of printing alt variable is used. If alt is 1 then printSpiralLevel() prints nodes from left to right else from right to left.
Non-Recursive solution of the problem is – Non-recursive Spiral Level Order Traversal
' void printSpiralLevel(struct node* root, int level, int alt); int height(struct node* node); /* Function to print spiral traversal of a tree*/ void printSpiral(struct node* root) { int h = height(root); int i; bool alt = false; for(i=1; i<=h; i++) { printSpiralLevel(root, i, alt); /*Revert alt to traverse next level in oppposite order*/ alt = !alt; } } /* Print nodes at a given level */ void printSpiralLevel(struct node* root, int level, int alt) { if(root == NULL) return; if(level == 1) printf("%d ", root->data); else if (level > 1) { if(alt) { printSpiralLevel(root->left, level-1, alt); printSpiralLevel(root->right, level-1, alt); } else { printSpiralLevel(root->right, level-1, alt); printSpiralLevel(root->left, level-1, alt); } } }
this is O(n^2). A O(n) solution is also possible using a queue. Only an additional space of O(n) would be required.