C++ Level Order Traversal of Binary Search Trees

This article explains level-order traversal/ Breadth First (BFS) traversal of binary search tree with a sample implementation in C++.

Level order traversal/ Breadth First (BFS) traversal of binary search tree

• Level order traversal is also referred as Breadth First (BFS)/ Width First tree traversals.
• In simple terms every node of a level is visited before going to the lower level.

Traversal of the above binary tree in level order produces the following result.

30 10 40 20 50

Traversal in level order is usually done with assitance of queue with the following steps:

• Add the root node to the queue and then repeat the following if queue is not empty.
• Dequeue a node from the front of queue and visit it.
• Enqueue the node's children from left to right.

Level order traversal of binary search tree implementation

#include <iostream>
#include <queue>
using namespace std;

// Node class
class Node {
    int key;
    Node* left;
    Node* right;
public:
    Node() { key=-1; left=NULL; right=NULL; };
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
};

// Tree class
class Tree {
     Node* root;
public:
     Tree();
     ~Tree();
     Node* Root() { return root; };
     void addNode(int key);
     void levelOrder(Node* n);
private:
     void addNode(int key, Node* leaf);
     void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
     root = NULL;
}

// Destructor
Tree::~Tree() {
     freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
       freeNode(leaf->Left());
       freeNode(leaf->Right());
       delete leaf;
    }
}

// Add a node
void Tree::addNode(int key) {
     // No elements. Add the root
     if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
    root = n;
     }
     else {
    cout << "add other node ... " << key << endl;
    addNode(key, root);
     }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
      addNode(key, leaf->Left());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
      addNode(key, leaf->Right());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setRight(n);
       }
    }
}

// Print the tree level-order assisted by queue
void Tree::levelOrder(Node* n) {
   // Create a queue
   queue<Node*> q;

   // Push the root
   q.push(n);

   while ( ! q.empty() )
   {
       // Dequeue a node from front
       Node* v = q.front();
       cout << v->Key() << " ";

       // Enqueue the left children
       if ( v->Left() != NULL )
            q.push(v->Left());

       // Enqueue the right children
       if ( v->Right() != NULL )
            q.push(v->Right());

       // Pop the visited node
       q.pop();
   }
}

// Test main program
int main() {
   Tree* tree = new Tree();
   tree->addNode(30);
   tree->addNode(10);
   tree->addNode(20);
   tree->addNode(40);
   tree->addNode(50);

   cout << "Level order traversal" << endl;
   tree->levelOrder(tree->Root());
   cout << endl;

   delete tree;
   return 0;
}

OUTPUT:-

add root node ... 30
add other node ... 10
add other node ... 20
add other node ... 40
add other node ... 50
Level order traversal
30 10 40 20 50