In this article I will show you how to traverse a tree in zigzag manner
// zigzag trav for tree
--->
// 12
// / \
<------------
// 9 15
// / \
------------>
// 4 10
// output :- 12 15 9 4 10
#include<iostream>
#include<stack>
using namespace std;
class Node
{
public:
int data;
Node *right,*left;
Node(int data)
{
this->data=data;
right=left=NULL;
}
};
void zigzagtrav(Node *root)
{
stack<Node*> curr;
stack<Node*> next;
bool leftToright=true;
curr.push(root);
while(!curr.empty())
{
Node *tmp=curr.top();
curr.pop();
if(tmp)
{
cout<<tmp->data<<" ";
if(leftToright)
{
next.push(tmp->left);
next.push(tmp->right);
}
else
{
next.push(tmp->right);
next.push(tmp->left);
}
}
if(curr.empty())
{
leftToright=!leftToright;
swap(curr,next);
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("../input.txt", "r", stdin);
freopen("../output.txt", "w", stdout);
#endif
Node *root=new Node(12);
root->right=new Node(15);
root->left=new Node(9);
root->left->left=new Node(4);
root->left->right=new Node(10);
zigzagtrav(root);
return 0;
}
here we are using two stacks
-
curr
which is to store our current node -
next
which is to store the next node - here the
leftToright
is to check that are we are printing the nodes left-to-right or right-to-left if the variable is true then we are printing the nodes left to right else print right-to-left. - Here if
leftToright
is true we are pushing the current left and then right node to next stack else push current right and then left node to next stack. - and checking if the curr node is empty swap the stack with next stack and toggle the
leftToright
variable.
Do it until both stack is empty.
Top comments (0)