Zig zag traversal of a binary search tree

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

The approach:-

1. Need assistance of two stacks. One for the even level and another one for odd level. Root node being treated as even node.
2. A level counter (could be a boolean) is used for traversal row (even or odd).
3. During even row traversal (left to right) push the child nodes to the odd stack with left node first and right next. And keep printing down the data of the current traversal node
4. During odd row traversal (left to right) push the child nodes to the even stack with right node first and left next. And keep printing down the data of the current traversal node
5. Start with root node being pushed to even stack. Continue until both the stacks are empty

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

#include <iostream>
#include <queue>
#include <stack>
#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 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) {
    stack<Node*> evenrow;
    stack<Node*> oddrow;
    evenrow.push(node);
    int level = 0;

    while ( ! evenrow.empty() || ! oddrow.empty() ) {

        if (! (level%2) ) {
            while (! evenrow.empty()) {
                Node* tmp = evenrow.top();
                evenrow.pop();
                cout << tmp->data() << " ";
                if ( tmp->left() )
                    oddrow.push(tmp->left());
                if ( tmp->right() )
                    oddrow.push(tmp->right());
            }
        } else {
            while (! oddrow.empty()) {
                Node* tmp = oddrow.top();
                oddrow.pop();
                cout << tmp->data() << " ";
                if ( tmp->right() )
                    evenrow.push(tmp->right());
                if ( tmp->left() )
                    evenrow.push(tmp->left());
            }
        }
        level++;
    }
    cout << endl;
}

// Test program
int 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 200 350 550 700 750 250 150 800