Level order traversal of a binary tree

Given a binary tree, we have to print the data level wise.

For example level order traversal of the following tree produces the sequence 5,3,8,2,4,6,1,7.

The hint to solve this problem is to use a Queue data structure. We start by inserting the root node into the queue. Until the queue is empty, we remove the first element from the queue and insert it’s left and right children at the last.

This will give us the level order traversal of the binary tree. For example look at the queue state at each iteration.

3,8

8,2,4

2,4,6

4,6,1

…

Here is the C++ program which contains the level order traversal function.

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

	class BSTNode
	{
	int data;
	BSTNode *left;
	BSTNode *right;

	public:
	//single param constructor
	BSTNode(int d):data(d), left(NULL), right(NULL)
	{
	}

	BSTNode(int d, BSTNode l, BSTNode r):data(d), left(l), right(r)
	{
	}

	int getData()
	{
	return data;
	}

	void setData(int d)
	{
	data = d;
	}

	BSTNode* getLeft()
	{
	return left;
	}

	void setLeft(BSTNode *l)
	{
	left = l;
	}

	BSTNode* getRight()
	{
	return right;
	}

	void setRight(BSTNode *r)
	{
	right = r;
	}

	};

	class BinarySearchTree
	{
	BSTNode * root;
	public:
	BinarySearchTree():root(NULL)
	{
	}
	BSTNode * getRoot()
	{
	return root;
	}
	bool insert(int d)
	{
	if( root == NULL ) // if tree is empty
	{
	root = new BSTNode(d);
	return true;
	}
	else
	{
	BSTNode *ptr = root;
	BSTNode *prev = NULL;

	while( ptr != NULL )
	{
	prev = ptr;

	if( ptr->getData() == d )//no duplicates allowed in BST
	return false;
	else if( ptr->getData() < d )
	{
	ptr = ptr->getRight();
	}
	else
	{
	ptr = ptr->getLeft();
	}
	}

	if( prev->getData() < d ) //to be added as right child?
	prev->setRight( new BSTNode(d) );
	else
	prev->setLeft( new BSTNode(d) );
	return true;
	}
	}

	void levelOrder()
	{
	queue<BSTNode *> nodeQueue;
	if( root != NULL )
	{
	nodeQueue.push( root );

	while( !nodeQueue.empty() )
	{
	BSTNode * ptr = nodeQueue.front();
	nodeQueue.pop();
	cout << ptr->getData() << " ";

	if( ptr->getLeft() != NULL )
	nodeQueue.push(ptr->getLeft());

	if( ptr->getRight() != NULL )
	nodeQueue.push(ptr->getRight());
	}
	}
	}

	};

	int main()
	{
	BinarySearchTree *bst = new BinarySearchTree();

	bst->insert(5);
	bst->insert(3);
	bst->insert(8);
	bst->insert(4);
	bst->insert(9);
	bst->insert(1);
	bst->insert(10);
	bst->insert(2);
	bst->insert(6);
	bst->insert(7);

	bst->levelOrder();
	cout<<endl;

	return 0;
	}

view raw LevelOrderTraversal.cpp hosted with

by GitHub

Leave a Reply Cancel reply