Level order traversal of a binary search tree with a new line after each level

Write a program to do level order printing of a binary search tree with a new line after each level

The approach:-

1. As in the regular level order traversal we need a queue.
2. Push the root node into the queue and set the current level as 1.
3. When queue not empty dequeue a node and print the node and decrement the current level.
4. Push the left and right child if available and increment the next level.
5. If current level is zero print a new line and reset the current value to next level.

C++ program to do level order printing of a binary search tree with a new line after each level

#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 levelorder(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::levelorder(Node* node) {
    queue<Node*> q;
    q.push(node);

    int currentLevel = 1;
    int nextLevel = 0;

    while ( ! q.empty() ) {
        Node* tmp = q.front();
        q.pop();
        currentLevel--;

        cout << tmp->data() << " ";

        if ( tmp->left() ) {
            q.push(tmp->left());
            nextLevel++;
        }

        if ( tmp->right() ) {
            q.push(tmp->right());
            nextLevel++;
        }

        if ( currentLevel == 0 ) {
            cout << endl;
            currentLevel = nextLevel;
            nextLevel = 0;
        }
    }

    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->levelorder(t->root());

    delete t;
}

Output:-

500
300 600
200 350 550 700
150 250 750
800