COUNTSORT

#include <bits/stdc++.h>

using namespace std;

vector<int> countSort(vector<int>& inputArray)

int N = inputArray.size();

int M = 0;

for (int i = 0; i < N; i++)

M = max(M, inputArray[i]);

// Initializing countArray[] with 0

vector<int> countArray(M + 1, 0);

for (int i = 0; i < N; i++)

countArray[inputArray[i]]++;

for (int i = 1; i <= M; i++)

countArray[i] += countArray[i - 1];

vector<int> outputArray(N);

for (int i = N - 1; i >= 0; i--)

outputArray[countArray[inputArray[i]] - 1]

= inputArray[i];

countArray[inputArray[i]]--;

return outputArray;

int main()

vector<int> inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 };

vector<int> outputArray = countSort(inputArray);

for (int i = 0; i < inputArray.size(); i++)

cout << outputArray[i] << " ";

return 0;
Q1. IMPLEMENT INSERTION SORT AND REPORT THE NUMBER OF COMPARISONS.

#include<iostream>

using namespace std;

void insertionSort(int arr[], int n, int &comparisons) {

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) {

comparisons++;

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

int main()

int arr[] = {12, 11, 13, 5, 6};

int n = sizeof(arr) / sizeof(arr[0]);

int comparisons = 0;

insertionSort(arr, n, comparisons);

cout << "Sorted array is: \n";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << "\nNumber of comparisons: " << comparisons;

return 0;

}
Q2. IMPLEMENT MERGE SORT AND REPORT THE NUMBER OF COMPARISONS.

#include<iostream>

using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {

int i, j, k;

int comparisons = 0;

i = left;

j = mid;

k = left;

while ((i <= mid - 1) && (j <= right)) {

comparisons++;

if (arr[i] <= arr[j]) {

temp[k++] = arr[i++];

} else {

temp[k++] = arr[j++];

while (i <= mid - 1)

temp[k++] = arr[i++];

while (j <= right)

temp[k++] = arr[j++];

for (i = left; i <= right; i++)

arr[i] = temp[i];

return comparisons;

int mergeSort(int arr[], int temp[], int left, int right)

int mid, comparisons = 0;

if (right > left) {

mid = (right + left) / 2;

comparisons += mergeSort(arr, temp, left, mid);

 comparisons += mergeSort(arr, temp, mid + 1, right);

comparisons += merge(arr, temp, left, mid + 1, right);

return comparisons;

int main()

int arr[] = {5,77,1,8,119,3};

int n = sizeof(arr) / sizeof(arr[0]);

int temp[n];

int comparisons = mergeSort(arr, temp, 0, n - 1);

cout << "Sorted array is: \n";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << "\nNumber of comparisons: " << comparisons;

return 0;

Q3. IMPLEMENT HEAP SORT AND REPORT THE NUMBER OF COMPARISONS.

#include<iostream>

using namespace std;

void heapify(int arr[], int n, int i, int &comparisons)

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest]) {

largest = left;

comparisons++;
 }

if (right < n && arr[right] > arr[largest]) {

largest = right;

comparisons++;

if (largest != i) {

swap(arr[i], arr[largest]);

heapify(arr, n, largest, comparisons);

void heapSort(int arr[], int n, int &comparisons) {

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i, comparisons);

for (int i = n - 1; i >= 0; i--) {

swap(arr[0], arr[i]);

heapify(arr, i, 0, comparisons);

int main() {

int arr[] = {5,1,3,99,6,};

int n = sizeof(arr) / sizeof(arr[0]);

int comparisons = 0;

heapSort(arr, n, comparisons);

cout << "Sorted array is: \n";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << "\nNumber of comparisons: " << comparisons;

return 0;

}
Q4. IMPLEMTN RANDOMIZED QUICK SORT AND THE REPORT THE NUMBER OF COMPARISONS.

#include<iostream>

using namespace std;

int comparisons = 0;

int partition(int arr[], int low, int high) {

int pivot = arr[low];

int i = low + 1;

for(int j = low + 1; j <= high; j++) {

comparisons++;

if(arr[j] < pivot) {

swap(arr[i], arr[j]);

i += 1;

swap(arr[low], arr[i - 1]);

return i - 1;

int randomized_partition(int arr[], int low, int high) {

int random = low + rand() % (high - low);

swap(arr[random], arr[low]);

return partition(arr, low, high);

void quickSort(int arr[], int low, int high) {

if(low < high) {

int pi = randomized_partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

int main() {

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr) / sizeof(arr[0]);

 quickSort(arr, 0, n - 1);

cout << "Sorted array: \n";

for(int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << "\nNumber of comparisons: " << comparisons;

return 0;

Q5. IMPLEMENT RADIX SORT.

#include<iostream>

using namespace std;

int getMax(int array[], int n) {

int maximum = array[0];

for (int i = 1; i < n; i++)

if (array[i] > maximum)

maximum = array[i];

return maximum;

void countingSort(int array[], int size, int place) {

const int max = 10;

int output[size];

int count[max];

for (int i = 0; i < max; ++i)

count[i] = 0;

for (int i = 0; i < size; i++)

count[(array[i] / place) % 10]++;

for (int i = 1; i < max; i++)

count[i] += count[i - 1];

for (int i = size - 1; i >= 0; i--) {

 output[count[(array[i] / place) % 10] - 1] = array[i];

count[(array[i] / place) % 10]--;

for (int i = 0; i < size; i++)

array[i] = output[i];

void RadixSort(int array[], int size) {

int max = getMax(array, size);

for (int place = 1; max / place > 0; place *= 10)

countingSort(array, size, place);

void printArray(int array[], int size) {

int i;

for (i = 0; i < size; i++)

cout << array[i] << " ";

cout << endl;

int main() {

int array[] = {121, 432, 564, 23, 1, 45, 788};

int n = sizeof(array) / sizeof(array[0]);

RadixSort(array, n);

printArray(array, n);

Q6 SEARCHING TECHNIQUE

(A) LINEAR SEACH

#include <iostream>

using namespace std;

int linearSearch(int arr[], int n, int x) {

for(int i = 0; i < n; i++) {

if(arr[i] == x) {

return i; // return the index of the found element

return -1; // return -1 if the element is not found

int main() {

int arr[] = {2, 3, 4, 10, 40};

int x = 10;

int n = sizeof(arr) / sizeof(arr[0]);

int result = linearSearch(arr, n, x);

(result == -1) ? cout << "Element is not present in array" : cout << "Element is present at index " << result;

return 0;

(B) BINARY SEARCH

#include<iostream>

using namespace std;

int binarySearch(int arr[], int l, int r, int x) {

while (l <= r) {

int m = l + (r - l) / 2;

if (arr[m] == x)

return m;

if (arr[m] < x)

l = m + 1;

else
 r = m - 1;

return -1;

int main() {

int arr[] = {2, 3, 4, 10, 40};

int x ;

cout<<"Enter number you want to search";

cin>>x;

int n = sizeof(arr) / sizeof(arr[0]);

int result = binarySearch(arr, 0, n - 1, x);

(result == -1) ? cout << "Element is not present in array"

: cout << "Element is present at index " << result;

return 0;

Q7. RECURSIVE FUNCTIONS.

1. FIBONACCI SERIES

#include<iostream>

using namespace std;

int fibonacci(int n) {

if (n <= 1)

return n;

else

return fibonacci(n - 1) + fibonacci(n - 2);

int main() {

int n ;

cout<<"Enter a number for fibbo series";

 cin>>n;

cout << "Fibonacci Series up to " << n << " terms:\n";

for(int i = 0; i < n; i++) {

cout << fibonacci(i) << ", ";

return 0;

(B) FACTORIAL

#include<iostream>

using namespace std;

int factorial(int n) {

if(n > 1)

return n * factorial(n - 1);

else

return 1;

int main() {

int num;

cout<<"Enter Number for Factorial";

cin>> num;

cout << "Factorial of " << num << " is " << factorial(num);

return 0;

}
Q8. STACK AND QUEUE USING LINKED LIST AND ARRAY

1. STACK USING LINKED LIST

#include <iostream>

#define MAX_size 10

using namespace std;

class stackNode

public:

int data;

stackNode *next;

};

// int size =0;

class stack

stackNode *top;

int size;

public:

stack()

top = NULL;

size = 0;

bool isfull();

bool isempty();

void push(int);

void pop();

void peek();

void display();

};

bool stack::isfull()

if (size == MAX_size)

return true;
 else

return false;

bool stack::isempty()

if (top == NULL || size == 0)

return true;

else

return false;

void stack::push(int num)

if (isfull())

cout << "stack is full." << endl;

return;

else

stackNode *newNode = new stackNode;

newNode->data = num;

newNode->next = top;

top = newNode;

size++;

void stack::pop()

if (isempty())

cout << "stack is empty." << endl;

return;

}
 else

stackNode *ptr = top;

top = top->next;

cout << "Deleted Node:" << ptr->data << endl;

delete (ptr);

cout << endl;

size--;

void stack::peek()

cout << "Top node element:" << top->data;

cout << endl;

void stack::display()

stackNode *ptr = top;

while (ptr != NULL)

cout << ptr->data << "->";

ptr = ptr->next;

cout << endl;

int main()

stack s1;

int ch;

do

cout << ".......Stack Using Linked List......." << endl;

cout << "1.Insert an element into the Stack:" << endl;

 cout << "2.Delete an element from the Stack:" << endl;

cout << "3.Peek into the Stack:" << endl;

cout << "4.Display the Stack:" << endl;

cout << "5.Exit." << endl;

cout << "Enter your choice:";

cin >> ch;

switch (ch)

case 1:

int num;

cout << "Enter the element :";

cin >> num;

s1.push(num);

break;

case 2:

s1.pop();

break;

case 3:

s1.peek();

break;

case 4:

s1.display();

break;

case 5:

cout << "Exiting the program." << endl;

break;

default:

cout << "Enter the valid choice." << endl;

} while (ch != 5);

}
STACK USING ARRAY

#include <iostream>

using namespace std;

#define MAX_STACK_SIZE 5

class Stack

private : int stk[MAX_STACK_SIZE];

int top;

public : Stack()

top = 0;

bool isFull()

if(top==MAX_STACK_SIZE-1)

return 1;

else

return 0;

bool isEmpty()

if(top==-1)

return 1;

else

return 0;

void push(int num)

{

if(isFull())

cout<<"\nOverflow Condition : Maximum limit reached.\n";

return;

else

stk[++top]=num;

int pop()

if(isEmpty())

cout<<"\nUnderflow Condition : No element in the Stack\n";

return -1;

else

return (stk[top--]);

void peek()

cout<<"\nTopmost Element : "<<stk[top]<<endl;

void display(int i)

for(int j=i; j>0; j--)

cout<<stk[j]<<"\t";

cout<<endl;

}
 };

int main() {

Stack s;

int i=0;

int num = 0;

do{

cout<<"\nSelect an option : \n1.Push\t2.Pop\t3.Peek\t4.Display\t5.Exit\t---> ";

cin>>num;

cout<<endl;

switch(num)

case 1: //for Push

++i;

int val;

cout<<"\nEnter the value: ";

cin>>val;

s.push(val);

break;

case 2: //for Pop

cout<<"\nPopped Element : "<<s.pop()<<endl;

break;

case 3: //for Peek

s.peek();

break;

case 4: //for displaying elements

s.display(i);

break;

case 5: //exit

exit(0);

cout<<"You are out of the program now :) ......";

default: cout<<"\nEnter a valid input!!\n";

}
 } while(num!=5);

return 0;

2. QUEUE USING LINKED LIST CODE :

#include<iostream>

#define MAX_SIZE 10

using namespace std;

class qNode{

public: int data;

qNode *next;

qNode(){next=NULL;}

};

class queue

qNode *rear, *front;

int size;

public: queue(){rear=front=NULL;size =0;}

void enqueue(int);

void dequeue();

bool isfull();

bool isempty();

void peek();

void display();

};

bool queue::isfull(){return ((size == MAX_SIZE -1));}

bool queue::isempty(){return ((size == 0));}

void queue::enqueue(int num)

{
 qNode *newNode= new qNode;

newNode -> data= num;

if(isfull())

cout<<"Queue is full."<<endl;

else if(front == NULL)

front = rear = newNode;

else

rear->next = newNode;

rear =newNode;

}size++;

void queue::dequeue()

qNode *ptr;

if (isempty())

cout<<"Queue is empty."<<endl;

else

ptr =front;

front = front->next;

cout<<"Deleted :"<<ptr->data;

cout<<endl;

delete ptr;

size--;

void queue::peek(){cout<<"Front Element is :"<<front ->data;cout<<endl;}

void queue::display()

qNode *ptr = front;

while (ptr !=rear)

{
 cout<<ptr->data<<"->";

ptr=ptr->next;

cout<<rear->data;

cout<<endl;

int main()

queue q1;

int ch;

do

cout<<".......Queue Using Linked List......."<<endl;

cout<<"1.Insert an element into the queue:"<<endl;

cout<<"2.Delete an element from the queue:"<<endl;

cout<<"3.Peek into the queue:"<<endl;

cout<<"4.Display the queue:"<<endl;

cout<<"5.Exit."<<endl;

cout<<"Enter the choice:";

cin>>ch;

switch(ch)

case 1:int num;cout<<"Enter the element :";

cin>>num;

q1.enqueue(num);

break;

case 2: q1.dequeue();

break;

case 3:q1.peek();

break;

case 4: q1.display();

break;

case 5: cout<<"Exiting the program."<<endl;

 break;

default:cout<<"Enter the valid choice."<<endl;

}while(ch!=5);

QUEUE USING ARRAY CODE:

#include <iostream>

#define MAX_SIZE 10

using namespace std;

class queue{

int front,rear,que[MAX_SIZE];

public :

queue(){front=rear=-1;}

bool isfull(){if (front == 0 && rear == MAX_SIZE -1)

return true;

else

return false;

bool isempty(){if (front ==-1 || front>rear)

return true;

else

return false;

void enqueue(int num)

if (isfull())

cout<<"Queue is full."<<endl;

else{
 if(front ==-1)

front =0;

que[++rear]=num;

void dequeue()

int num;

if (isempty())

cout<<"Queue is empty."<<endl;

else

num = que[front];

if (front==rear)

front=-1;

else

front++;

cout<<"Deleted element:"<<num<<endl;

void display()

cout<<"Queue elements are:"<<endl;

for (int i =front; i<=rear;i++)

cout<<que[i]<<" ";

cout<<endl;

void peek()

cout<<"Front Element:"<<que[front]<<endl;

}};

int main()

{ queue q1;
 int ch;

do {

cout<<"1) Insert element to queue"<<endl;

cout<<"2) Delete element from queue"<<endl;

cout<<"3) Display all the elements of queue"<<endl;

cout<<"4) Peek the first element of queue"<<endl;

cout<<"5) Exit"<<endl;

cout<<"Enter your choice : "<<endl;

cin>>ch;

switch (ch) {

case 1: int n; cout<<"Enter the element: ";

cin >> n;

q1.enqueue(n);

break;

case 2: q1.dequeue();

break;

case 3: q1.display();

break;

case 4: q1.peek();

break;

case 5: cout<<"Exiting the program..."<<endl;

break;

default: cout<<"Invalid choice"<<endl;

} while(ch!=5);

return 0;

Q9 IMPLEMENTATION OF SINGLE, DOUBLE AND CIRCULAR LINKED LIST.

1. SINGLE LINKED LIST

#include <iostream>

using namespace std;

class Node

public:

int data;

Node *next;

Node() { next = 0; }

};

class SLL

Node *head;

public:

SLL() { head = NULL; }

void addatbeg(int);

void addatend(int);

void addatloc(int, int);

void delfrombeg();

void delfromend();

void delfromloc(int);

void display();

};

void SLL::addatbeg(int num)

Node *newNode = new Node();

newNode->data = num;

newNode->next = head;

head = newNode;

void SLL::addatend(int num)

Node *newNode = new Node();

 newNode->data = num;

if (head == NULL)

head = newNode;

else

Node *ptr = head;

while (ptr->next != NULL)

ptr = ptr->next;

ptr->next = newNode;

void SLL::addatloc(int num, int loc)

Node *newNode = new Node();

newNode->data = num;

Node *ptr = head;

for (int i = 1; i < loc - 1; i++)

ptr = ptr->next;

newNode->next = ptr->next;

ptr->next = newNode;

void SLL::delfrombeg()

if (head == NULL)

cout << "List is empty." << endl;

else

Node *ptr = head;

cout << "Deleted node is:" << ptr->data << endl;

head = head->next;

delete (ptr);

}
void SLL::delfromend()

if (head == NULL)

cout << "List is empty." << endl;

else

if (head->next == NULL)

cout << "Deleted node is:" << head->data << endl;

delete (head);

head = NULL;

else

Node *ptr = head;

while (ptr->next->next != NULL)

ptr = ptr->next;

cout << "Deleted node is:" << ptr->next->data << endl;

delete (ptr->next);

ptr->next = NULL;

void SLL::delfromloc(int loc)

if (head == NULL)

cout << "List is empty." << endl;

Node *ptr1 = head;

Node *ptr2;

for (int i = 1; i < loc; i++)

{
 ptr2 = ptr1;

ptr1 = ptr1->next;

cout << "Deleted node is :" << ptr1->data << endl;

ptr2->next = ptr1->next;

delete (ptr1);

void SLL::display()

if (head == NULL)

cout << "Nothing to show nothing to hide." << endl;

else

Node *ptr = head;

cout << "Linked List: ";

while (ptr != NULL)

cout << ptr->data << "->";

ptr = ptr->next;

cout << "NULL" << endl;

int main()

SLL singlinklist;

int ch;

cout << "++++++++++LINKED LIST+++++++++++" << endl;

do

cout << "1) Insert element at beginning" << endl;

cout << "2) Insert element at the end" << endl;

cout << "3) Insert element at a location" << endl;

cout << "4) Delete element at beginning" << endl;

cout << "5) Delete element at the end" << endl;

cout << "6) Delete element at a location" << endl;

cout << "7) Display all the elements" << endl;

cout << "8) Exit" << endl;

cout << "Enter your choice: " << endl;

cin >> ch;

switch (ch)

case 1:

int nb;

cout << "Enter the element: ";

cin >> nb;

singlinklist.addatbeg(nb);

break;

case 2:

int ne;

cout << "Enter the element: ";

cin >> ne;

singlinklist.addatend(ne);

break;

case 3:

int nl;

cout << "Enter the element: ";

cin >> nl;

int idx;

cout << "Enter the location: ";

cin >> idx;

singlinklist.addatloc(nl, idx);

break;

case 4:

singlinklist.delfrombeg();

break;
 case 5:

singlinklist.delfromend();

break;

case 6:

int i;

cout << "Enter the location: ";

cin >> i;

singlinklist.delfromloc(i);

break;

case 7:

singlinklist.display();

break;

case 8:

cout << "Exiting the program..." << endl;

break;

default:

cout << "Invalid choice" << endl;

} while (ch != 8);

2. DOUBLY LINKED LIST

#include <iostream>

using namespace std;

class dNode

public:

int data;

dNode *prev;
 dNode *next;

};

class DoublyLinkedList

public:

dNode *head;

DoublyLinkedList() { head = NULL; }

void addatbeg(int);

void addatend(int);

void delfrombeg();

void delfromend();

void display();

};

void DoublyLinkedList ::addatbeg(int num)

dNode *temp = new dNode();

temp->data = num;

if (head == NULL)

temp->prev = NULL;

temp->next = NULL;

head = temp;

else

temp->prev = NULL;

temp->next = head;

head->prev = temp;

head = temp;

void DoublyLinkedList ::addatend(int num)

{
 dNode *temp = new dNode();

temp->data = num;

if (head == NULL)

temp->prev = NULL;

temp->next = NULL;

head = temp;

else

dNode *ptr = head;

while (ptr->next != NULL)

ptr = ptr->next;

temp->next = NULL;

temp->prev = ptr;

ptr->next = temp;

void DoublyLinkedList::delfrombeg()

dNode *ptr;

if (head == NULL)

cout << "List is empty" << endl;

return;

if (head->next == NULL)

cout << "Deleted Node" << head->data;

delete (head);

else

{
 ptr = head;

head = head->next;

head->prev = NULL;

cout << "Deleted Node is " << ptr->data;

delete (ptr);

void DoublyLinkedList::delfromend()

dNode *ptr;

if (head == NULL)

cout << "List is empty." << endl;

return;

if (head->next == NULL)

cout << "Deleted Node is " << head->data << endl;

delete (head);

return;

else

ptr = head;

dNode *ptr1 = head->next;

while (ptr1->next != NULL)

ptr = ptr1;

ptr1 = ptr1->next;

cout << "Deleted Node is " << ptr1->data;

delete (ptr1);

ptr->next = NULL;
 }

void DoublyLinkedList::display()

dNode *ptr = head;

cout << "Elements of list are " << endl;

while (ptr != NULL)

cout << ptr->data << " -> ";

ptr = ptr->next;

cout << "nullptr" << endl;

int main()

DoublyLinkedList l1;

int ch;

cout << "++++++++++ DOUBLYLINKED LIST+++++++++++" << endl;

do

cout << "1) Insert element at beginning" << endl;

cout << "2) Insert element at the end" << endl;

cout << "3) Delete element at beginning" << endl;

cout << "4) Delete element at the end" << endl;

cout << "5) Display all the elements" << endl;

cout << "6) Exit" << endl;

cout << "Enter your choice: " << endl;

cin >> ch;

switch (ch)

case 1:

int nb;

cout << "Enter the element: ";

 cin >> nb;

l1.addatbeg(nb);

break;

case 2:

int ne;

cout << "Enter the element: ";

cin >> ne;

l1.addatend(ne);

break;

case 3:

l1.delfrombeg();

break;

case 4:

l1.delfromend();

break;

case 5:

l1.display();

break;

case 6:

cout << "Exiting the program..." << endl;

break;

default:

cout << "Invalid choice" << endl;

} while (ch != 6);

(C) CIRCULAR LINKED LIST

#include<iostream>
using namespace std;

struct Node {

int data;

Node *next;

};

void addNode(Node **head_ref, int data) {

Node *newNode = new Node();

Node *temp = *head_ref;

newNode->data = data;

newNode->next = *head_ref;

if (*head_ref != NULL) {

while (temp->next != *head_ref)

temp = temp->next;

temp->next = newNode;

} else

newNode->next = newNode;

*head_ref = newNode;

void deleteNode(Node **head_ref, int key) {

if (*head_ref == NULL)

return;

Node *curr = *head_ref, *prev;

while (curr->data != key) {

if (curr->next == *head_ref) {

cout << "The node " << key << " is not in the list.\n";

return;

prev = curr;

curr = curr->next;

if (curr->next != *head_ref)

*head_ref = curr->next;

else if (curr == curr->next)

 *head_ref = NULL;

prev->next = curr->next;

delete curr;

void displayList(Node *head) {

Node *temp = head;

if (head != NULL) {

do {

cout << temp->data << " ";

temp = temp->next;

} while (temp != head);

int main() {

Node *head = NULL;

int choice, data;

while(1) {

cout << "\n1.Add Node\n2.Delete Node\n3.Display List\n4.Exit\nEnter your choice: ";

cin >> choice;

switch(choice) {

case 1:

cout << "Enter data: ";

cin >> data;

addNode(&head, data);

break;

case 2:

cout << "Enter the node to be deleted: ";

cin >> data;

deleteNode(&head, data);

break;

case 3:

cout << "Displaying the circular linked list:\n";

displayList(head);
 break;

case 4:

exit(0);

default:

cout << "Invalid choice! Please enter a valid option.";

return 0;

Q10. CREATION AND TRAVERSAL OF BINARY SEARCH TREE.

#include<iostream>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

};

Node* createNode(int data) {

Node* newNode = new Node();

if (!newNode) {

cout << "Memory error\n";

return NULL;

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

Node* insertNode(Node* root, int data) {

 if (root == NULL) {

root = createNode(data);

return root;

if (data < root->data)

root->left = insertNode(root->left, data);

else

root->right = insertNode(root->right, data);

return root;

void inorder(Node* temp) {

if (temp == NULL)

return;

inorder(temp->left);

cout << temp->data << " ";

inorder(temp->right);

void preorder(Node* temp) {

if (temp == NULL)

return;

cout << temp->data << " ";

preorder(temp->left);

preorder(temp->right);

void postorder(Node* temp) {

if (temp == NULL)

return;

postorder(temp->left);

postorder(temp->right);

cout << temp->data << " ";

int main() {

Node* root = NULL;

 int choice, data;

while(1) {

cout << "\n1.Add Node\n2.Inorder Traversal\n3.Preorder Traversal\n4.Postorder Traversal\n5.Exit\nEnter

your choice: ";

cin >> choice;

switch(choice) {

case 1:

cout << "Enter data: ";

cin >> data;

root = insertNode(root, data);

break;

case 2:

cout << "Inorder traversal: ";

inorder(root);

cout << "\n";

break;

case 3:

cout << "Preorder traversal: ";

preorder(root);

cout << "\n";

break;

case 4:

cout << "Postorder traversal: ";

postorder(root);

cout << "\n";

break;

case 5:

exit(0);

default:

cout << "Invalid choice! Please enter a valid option.";

return 0;
}