﻿ C++ Level Order Traversal of Binary Search Trees ~ Programming Tutorials by SourceTricks
Monday, May 9, 2011

## C++ Level Order Traversal of Binary Search Trees

### What is level-order traversal/ Breadth First (BFS) traversal of binary search tree?

This article explains level-order traversal/ Breadth First (BFS) traversal of binary search tree with a sample implementation in C++.
• 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.

• An example:

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.

### Demonstrate the level order traversal of binary search tree

``````#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 levelOrder(Node* n);
private:
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;
}
}

// 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;
}
}

void Tree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() ) {
if ( leaf->Left() != NULL )
else {
Node* n = new Node();
n->setKey(key);
leaf->setLeft(n);
}
}
else {
if ( leaf->Right() != NULL )
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();

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

delete tree;
return 0;
}
``````
``````
``````
OUTPUT:-
``````add root node ... 30
Level order traversal
30 10 40 20 50
``````

Name

Email *

Message *