StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Thursday, February 21, 2013

Zig zag traversal of a binary search tree

 February 21, 2013     Programming problems in CPP     No comments   

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
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk