DSA Lab assignment – 06
Name – Anurag Kumar Branch – CSE Core-I
Roll no- 25U020079 Date- 17/03/2026
Q1.) Write a C/C++ program to:
a) Create a Binary Search Tree by inserting n elements
provided by the user
b) Display the tree using:
o Inorder traversal
o Preorder traversal
o Postorder traversal
#include<iostream>
using namespace std;
struct Node{
int data;
Node *left,*right;
};
Node* createNode(int x){
Node* n=new Node();
n->data=x;
n->left=n->right=NULL;
return n;
}
Node* insert(Node* root,int x){
if(root==NULL) return createNode(x);
if(x<root->data) root->left=insert(root->left,x);
else root->right=insert(root->right,x);
return root;
}
void inorder(Node* root){
if(root){
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
void preorder(Node* root){
if(root){
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
void postorder(Node* root){
if(root){
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
int main(){
Node* root=NULL;
int n,x;
cout<<"Enter number of elements:";
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
root=insert(root,x);
}
cout<<"Inorder:";inorder(root);cout<<endl;
cout<<"Preorder:";preorder(root);cout<<endl;
cout<<"Postorder:";postorder(root);cout<<endl;
}
Q2.) Write a C/C++ program to delete a node from a Binary
Search Tree.
Your program must correctly handle all three cases:
a) Deletion of a leaf node
b) Deletion of a node with one child
c) Deletion of a node with two children
After deletion, display the inorder traversal.
#include<iostream>
using namespace std;
struct Node{
int data;
Node *left, *right;
};
Node* createNode(int x){
Node* n = new Node();
n->data = x;
n->left = n->right = NULL;
return n;
}
Node* insert(Node* root, int x){
if(!root) return createNode(x);
if(x < root->data) root->left = insert(root->left, x);
else root->right = insert(root->right, x);
return root;
}
Node* minValueNode(Node* root){
Node* temp = root;
while(temp && temp->left) temp = temp->left;
return temp;
}
Node* deleteNode(Node* root, int key){
if(!root) return root;
if(key < root->data) root->left = deleteNode(root->left, key);
else if(key > root->data) root->right = deleteNode(root-
>right, key);
else{
if(!root->left){
Node* t = root->right;
delete root;
return t;
}
else if(!root->right){
Node* t = root->left;
delete root;
return t;
}
Node* t = minValueNode(root->right);
root->data = t->data;
root->right = deleteNode(root->right, t->data);
}
return root;
}
void inorder(Node* root){
if(root){
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
int main(){
Node* root = NULL;
int n, x, key;
cout<<"Enter number of elements: ";
cin>> n;
for(int i=0 ; i<n ; i++){
cin>>x;
root = insert(root,x);
}
cout<<"Enter node to delete: "; cin>>key;
root = deleteNode(root, key);
cout<<"Inorder after deletion:"; inorder(root); cout<<endl;}
Q3.) Write a C/C++ program to find the Kth smallest element
in a Binary Search Tree.
#include<iostream>
using namespace std;
struct Node{
int data;
Node *left, *right;
};
Node* createNode(int x){
Node* n = new Node();
n->data = x;
n->left = n->right = NULL;
return n;
}
Node* insert(Node* root, int x){
if(!root) return createNode(x);
if(x < root->data) root->left = insert(root->left, x);
else root->right = insert(root->right, x);
return root;
}
void inorder(Node* root, int &k, int &res){
if(root){
inorder(root->left, k, res);
k--;
if(k==0) res = root->data;
inorder(root->right, k, res);
}
}
int main(){
Node* root = NULL;
int n, x, k, res=-1;
cout<<"Enter number of elements: ";
cin>>n;
for(int i=0; i<n; i++){
cin>>x;
root = insert(root, x);
}
cout<<"Enter K: ";
cin>>k;
int t = k;
inorder(root, t, res);
cout<<"Kth smallest element: "<< res << endl;
}