﻿ Zig zag traversal of binary search tree ~ Programming Tutorials by SourceTricks
Saturday, July 14, 2012

## 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 class
class 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 class
class Tree {
public:
Tree() { mRoot = NULL; }
~Tree() {}
Node* root() { return mRoot; }
void zigzag(Node *node);

private:

private:
Node* mRoot;
};

if ( mRoot == NULL ) {
Node* tmp = new Node();
tmp->setData(data);
mRoot = tmp;
}
else {
}
}

void Tree::addNode(Node* node, int data) {
if ( data <= node->data() ) {
if ( node->left() != NULL )
else {
Node* tmp = new Node();
tmp->setData(data);
tmp->setParent(node);
node->setLeft(tmp);
}
}
else {
if ( node->right() != NULL )
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 program
int main() {
Tree* t = new Tree();

t->zigzag(t->root());

delete t;
}```

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

Name

Email *

Message *