Spiral order Traversal of Binary Tree code in c++.

Given a Tree and we need to print the spiral order  traversal of the given tree.

By spiral Order Traversal We mean that alternate levels should be printed in alternate order .

for eg:- Level 0 to  be printed left to right
Level 1 from right to left. and so on

 

Let’s say given input tree is

The output for given tree is

A  B C  G F E D H I.

The observation one can make is that if level is odd we are printing the nodes left to right and if it is even we are printing them right to left.

Thus idea to be used is similar to what we do in level order traversal and additionally we need to maintain a counter which maintain level numbers so that printing can be done accordingly
Thus we maintain two stacks and one stack is used for printing left to right while other is used for printing right to left.\

Time complexity for this program is O(n) and same is also the space complexity.

Readers are requested to submit their code in the comment section below.

Code:-

[code language=”cpp”]

#include<bits/stdc++.h>

struct Treenode// definition of structure of tree node which has lchild child and rchild child
{
int val;
Treenode* lchild;
Treenode* rchild;
};

struct Treenode* newNode(int key)// function for new node creation
{
struct Treenode* newnode = (struct Treenode*)malloc(sizeof(struct Treenode));
newnode->val = key;
newnode->lchild = NULL;
newnode->rchild = NULL;

return(newnode);
}

// a function that prints the spiral order of tree
void spiralorder(Treenode* root)
{

if (root==NULL)
return; // since root is null we can move back

// declare two stacks
stack<Treenode*> s1;
stack<Treenode*> s2;

s1.push(root);

bool count = 0;
while (!s1.empty()) {

// pop out of stack
Treenode* temp = s1.top();
s1.pop();

// if not null
if (temp) {

// print the value i
cout << temp->val << " ";

// store data according to current
// order.
if (count%2==0) {
if (temp->lchild)
s2.push(temp->lchild);
if (temp->rchild)
s2.push(temp->rchild);
}
else {
if (temp->rchild)
s2.push(temp->rchild);
if (temp->lchild)
s2.push(temp->lchild);
}
}

if (s1.empty()) {
count++;
swap(s1, s2);
}
}
}

int main()
{
Treenode *root1 = newNode(232);
Treenode *root2 = newNode(232);// these part is concerned with creation of tree
// user can edit this as per wish
root1->lchild = newNode(231);
root1->rchild = newNode(231);
root1->lchild->lchild = newNode(431);
root1->lchild->rchild = newNode(531);

root2->lchild = newNode(231);
root2->rchild = newNode(331);
root2->lchild->lchild = newNode(431);
root2->lchild->rchild = newNode(513);

spiralorder(root)

getchar();
return 0;
}

[/code]