Tree Creation using Queue in C++
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
// ===================== STRUCTURE DEFINITION =====================
// Each node has: data, left child pointer, and right child pointer.
struct node
{
int data;
node* right;
node* left;
// Constructor to initialize a new node
node(int val)
{
data = val;
right = nullptr;
left = nullptr;
}
};
node* root = nullptr; // Global root pointer
// ===================== TREE CREATION =====================
// CreateTree() builds a binary tree level-wise (using a queue).
// -1 indicates that a node does not have a child.
void CreateTree()
{
queue<node*> q;
node* p;
node* t;
int x;
cout << "ENTER ROOT NODE: ";
cin >> x;
root = new node(x); // Create root node
[Link](root); // Push root into queue
// Use level order approach to insert children
while (![Link]())
{
p = [Link]();
[Link]();
cout << "Enter left child of " << p->data << " (enter -1 for
no child): ";
cin >> x;
if (x != -1)
{
t = new node(x);
p->left = t;
[Link](t);
}
cout << "Enter right child of " << p->data << " (enter -1 for
no child): ";
cin >> x;
if (x != -1)
{
t = new node(x);
p->right = t;
[Link](t);
}
}
}
// ===================== RECURSIVE TRAVERSALS =====================
// Inorder Traversal (LNR: Left → Node → Right)
// Visits all nodes in ascending order for a BST
void inorderTraversal(node* node)
{
if (node != nullptr)
{
inorderTraversal(node->left);
cout << node->data << " ";
inorderTraversal(node->right);
}
}
// Preorder Traversal (NLR: Node → Left → Right)
// Useful for copying the tree or prefix expression
void preorder(node* node)
{
if (node != nullptr)
{
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}
// Postorder Traversal (LRN: Left → Right → Node)
// Useful for deleting or freeing the tree memory
void postorder(node* node)
{
if (node != nullptr)
{
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
}
}
// ===================== ITERATIVE TRAVERSALS =====================
// 1. Iterative Preorder Traversal (NLR)
// Uses a stack instead of recursion.
void preorderIterative(node* root)
{
if (root == nullptr) return;
stack<node*> st;
[Link](root);
while (![Link]())
{
node* current = [Link]();
[Link]();
cout << current->data << " ";
// Push right first so left is processed first
if (current->right != nullptr)
[Link](current->right);
if (current->left != nullptr)
[Link](current->left);
}
}
// 2. Iterative Inorder Traversal (LNR)
// Uses a stack to simulate recursion
void inorderIterative(node* root)
{
if (root == nullptr) return;
stack<node*> st;
node* current = root;
while (current != nullptr || ![Link]())
{
// Reach the leftmost node of current
while (current != nullptr)
{
[Link](current);
current = current->left;
}
// Current is NULL, so process top node
current = [Link]();
[Link]();
cout << current->data << " ";
// Visit the right subtree
current = current->right;
}
}
// 3. Iterative Postorder Traversal (LRN)
// Trick: use two stacks or one stack + previous pointer method
void postorderIterative(node* root)
{
if (root == nullptr) return;
stack<node*> st1, st2;
[Link](root);
while (![Link]())
{
node* current = [Link]();
[Link]();
[Link](current);
if (current->left)
[Link](current->left);
if (current->right)
[Link](current->right);
}
// Print in reverse order (left-right-node)
while (![Link]())
{
cout << [Link]()->data << " ";
[Link]();
}
}
// 4. Level Order Traversal (Breadth-First Search)
// Uses queue to process nodes level by level
void levelOrder(node* root)
{
if (root == nullptr) return;
queue<node*> q;
[Link](root);
while (![Link]())
{
node* current = [Link]();
[Link]();
cout << current->data << " ";
if (current->left != nullptr)
[Link](current->left);
if (current->right != nullptr)
[Link](current->right);
}
}
// ===================== MAIN FUNCTION =====================
int main()
{
CreateTree();
cout << "\n\nRECURSIVE TRAVERSALS:\n";
cout << "Inorder: ";
inorderTraversal(root);
cout << "\nPreorder: ";
preorder(root);
cout << "\nPostorder: ";
postorder(root);
cout << "\n\nITERATIVE TRAVERSALS:\n";
cout << "Preorder: ";
preorderIterative(root);
cout << "\nInorder: ";
inorderIterative(root);
cout << "\nPostorder: ";
postorderIterative(root);
cout << "\n\nLEVEL ORDER TRAVERSAL:\n";
levelOrder(root);
cout << "\n";
return 0;
}
Notes (for future reference)
• Preorder (NLR): Root → Left → Right
➤ Used to create a copy of the tree or generate prefix expressions.
• Inorder (LNR): Left → Root → Right
➤ Gives sorted order of elements for Binary Search Trees (BSTs).
• Postorder (LRN): Left → Right → Root
➤ Used for deleting/freeing nodes (bottom-up).
• Level Order (Breadth-First Search):
➤ Processes tree level by level, using a queue.
• Recursive traversals use the call stack automatically,
while iterative traversals use an explicit stack/queue.
• Queue → Level order traversal (FIFO structure).
• Stack → Depth-first traversals (LIFO structure).