# Zig zag traversal of binary search tree

### Write a program to do zig zag traversal of a binary search tree

The approach:-

1. Need assistance of a queue.
2. Same as level order traversal except that instead of pushing the left sub-tree into the queue first push the right tree sub-tree.

#### C++ program to do zig zag traversal of a binary search tree

`#include <iostream>#include <queue>#include <cstdlib>using namespace std;// Node classclass Node {public:Node() { mData = -1; mParent = NULL; mLeft = NULL; mRight = NULL; }~Node() {}int data() { return mData; }void setData(int data) { mData = data; }Node* left() { return mLeft; }void setLeft(Node* left) { mLeft = left; }Node* right() { return mRight; }void setRight(Node* right) { mRight = right; }Node* parent() { return mParent; }void setParent(Node* parent) { mParent = parent; }private:int mData;Node* mLeft;Node* mRight;Node* mParent;};// Tree classclass Tree {public:Tree() { mRoot = NULL; }~Tree() {}Node* root() { return mRoot; }void addNode(int data);void zigzag(Node *node);private:void addNode(Node* node, int data);private:Node* mRoot;};void Tree::addNode(int data) {if ( mRoot == NULL ) {Node* tmp = new Node();tmp->setData(data);mRoot = tmp;}else {addNode(mRoot, data);}}void Tree::addNode(Node* node, int data) {if ( data <= node->data() ) {if ( node->left() != NULL )addNode(node->left(), data);else {Node* tmp = new Node();tmp->setData(data);tmp->setParent(node);node->setLeft(tmp);}}else {if ( node->right() != NULL )addNode(node->right(), data);else {Node* tmp = new Node();tmp->setData(data);tmp->setParent(node);node->setRight(tmp);}}}void Tree::zigzag(Node* node) {queue<Node*> q;q.push(node);while ( ! q.empty() ) {Node* tmp = q.front();q.pop();cout << tmp->data() << " ";if ( tmp->right() )q.push(tmp->right());if ( tmp->left() )q.push(tmp->left());}cout << endl;}// Test programint main() {Tree* t = new Tree();t->addNode(500);t->addNode(300);t->addNode(600);t->addNode(550);t->addNode(700);t->addNode(750);t->addNode(200);t->addNode(150);t->addNode(250);t->addNode(350);t->addNode(800);t->zigzag(t->root());delete t;}`

Output:-

`500 600 300 700 550 350 200 750 250 150 800`