Level order traversal using queue in c++
C++ program for Level order traversal using queue. Here problem description and other solutions.
// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Level order tree traversal using queue
*/
// Binary Tree Node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
// Create Q node
class QNode
{
public:
TreeNode *data;
QNode *next;
QNode(TreeNode *node)
{
this->data = node;
this->next = nullptr;
}
};
class MyQueue
{
public:
QNode *head;
QNode *tail;
int count;
MyQueue()
{
this->head = nullptr;
this->tail = nullptr;
this->count = 0;
}
int size()
{
return this->count;
}
bool isEmpty()
{
return this->count == 0;
}
// Add new node of queue
void enqueue(TreeNode *value)
{
// Create a new node
QNode *node = new QNode(value);
if (this->head == nullptr)
{
// Add first element into queue
this->head = node;
}
else
{
// Add node at the end using tail
this->tail->next = node;
}
this->count++;
this->tail = node;
}
// Delete a element into queue
void dequeue()
{
if (this->head == nullptr)
{
// Empty Queue
return;
}
QNode *t = this->head;
// Visit next node
this->head = this->head->next;
this->count--;
if (this->head == nullptr)
{
// When deleting a last node of linked list
this->tail = nullptr;
}
delete t;
}
// Get front node
TreeNode *peek()
{
if (this->head == nullptr)
{
return nullptr;
}
return this->head->data;
}
};
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = nullptr;
}
void levelOrder()
{
if (this->root != nullptr)
{
MyQueue *q = new MyQueue();
// Add first node
q->enqueue(this->root);
TreeNode *node = this->root;
while (q->isEmpty() == false && node != nullptr)
{
if (node->left != nullptr)
{
// Add left child node
q->enqueue(node->left);
}
if (node->right != nullptr)
{
// Add right child node
q->enqueue(node->right);
}
// Display level node
cout << " " << node->data;
// Remove current node
q->dequeue();
// Get new head
node = q->peek();
}
}
else
{
cout << "Empty Tree" << endl;
}
}
};
int main()
{
// Create new tree
BinaryTree *tree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
/ / \
7 8 9
*/
// Adding tree nodes
tree->root = new TreeNode(1);
tree->root->left = new TreeNode(2);
tree->root->right = new TreeNode(3);
tree->root->right->right = new TreeNode(6);
tree->root->right->left = new TreeNode(5);
tree->root->left->left = new TreeNode(4);
tree->root->left->left->left = new TreeNode(7);
tree->root->right->left->left = new TreeNode(8);
tree->root->right->left->right = new TreeNode(9);
// Display level order element
tree->levelOrder();
return 0;
}
Output
1 2 3 4 5 6 7 8 9
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment