Saturday, July 14, 2012

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

1 comment :

  1. Wrong Code , pls correct yourself as this traversal is not called zig zag traversal , u have to have use a stack, queue wont help

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top