Lab No.

12

Course Name: Data Structures and Algorithms

Submitted by: Rabia Sarfraz
Roll No.: 2330-0070
Class Section: FA23/BS(SE)
Submitted to: Sir Bilal
DATE: 11th January, 2025
Task No. 01:
You are a software engineer working on a data management system for a
library. The system uses a Binary Search Tree to store book IDs, which are
unique integers. To keep the tree balanced and efficient, you must implement
a delete function that can remove a book ID from the tree while maintaining
its structural integrity.
Problem Description: The delete operation in a Binary Search Tree involves
three cases:
1. Leaf Node Deletion: Deleting a node with no children.
2. Single Child Deletion: Deleting a node with one child.
3. Two Children Deletion: Deleting a node with two children. Replace the
node with either its in-order predecessor or in-order successor to maintain
the BST properties.
Your task is to implement a delete() function in the BST class and test it
thoroughly with various scenarios
Code:
#include <iostream>
#include <string>
using namespace std;
// Book structure
struct Book {
string ISBN;
string name;
string author;
int edition;
// Constructor
Book() : ISBN(""), name(""), author(""), edition(0) {}
Book(string isbn, string n, string a, int e) : ISBN(isbn), name(n), author(a),
edition(e) {}
// Input function
void input()
{
cout << "Enter ISBN: ";
cin >> ISBN;
cin.ignore(); // Ignore newline character
cout << "Enter book name: ";
getline(cin, name);
cout << "Enter author name: ";
getline(cin, author);
cout << "Enter edition: ";
cin >> edition;
}
// Output function
void output() const
{
cout << "ISBN: " << ISBN << ", Book Name: " << name
<< ", Author: " << author << ", Edition: " << edition << endl;
}
// Comparison operators
bool operator<(const Book &b) const
{
return ISBN < b.ISBN;
}
bool operator>(const Book &b) const
{
 return ISBN > b.ISBN;
}
bool operator==(const Book &b) const
{
return ISBN == b.ISBN;
}
};
// Node structure for the BST
struct Node{
Book book;
Node *left;
Node *right;
Node(const Book &b) : book(b), left(NULL), right(NULL) {}
};
// Binary Search Tree Class
class BST{
private:
Node *root;
Node *insertNode(Node *node,const Book &book)
{
if (node==NULL)
{
return new Node(book);
}
if (book<node->book)
{
 node->left=insertNode(node->left,book);
} else if (book>node->book)
{
node->right=insertNode(node->right,book);
}
return node;
}
bool searchNode(Node *node, const string &isbn) const
{
if (node==NULL)
{
return false;
}
if(node->book.ISBN==isbn)
{
return true;
}
if(isbn < node->book.ISBN)
{
return searchNode(node->left, isbn);
}
return searchNode(node->right, isbn);
}

Node *deleteNode(Node *node, const string &isbn)

{
if (node==NULL)
{
return node;
}
if (isbn < node->book.ISBN)
{
node->left = deleteNode(node->left,isbn);
}
else if(isbn>node->book.ISBN)
{
node->right=deleteNode(node->right,isbn);
}
else
{
if (node->left==NULL)
{
Node *temp=node->right;
delete node;
return temp;
}
else if(node->right==NULL)
{
Node *temp = node->left;
delete node;
return temp;
}
 Node *temp=findMin(node->right);
node->book=temp->book;
node->right=deleteNode(node->right, temp->book.ISBN);
}
return node;
}

Node *findMin(Node *node) const

{
while (node&&node->left!=NULL)
{
node=node->left;
}
return node;
}

void inorderTraversal(Node *node) const

{
if(node!=NULL)
{
inorderTraversal(node->left);
node->book.output();
inorderTraversal(node->right);
}
}
public:
 BST() : root(NULL){}

void insert(const Book &book)

{
root = insertNode(root, book);
}

bool search(const string &isbn) const

{
return searchNode(root, isbn);
}
void deleteValue(const string &isbn)
{
root = deleteNode(root, isbn);
}

void inorder() const

{
inorderTraversal(root);
cout << endl;
}
};
// Main function
int main()
{
BST tree;
 Book b1("123", "Book A", "Author A", 1);
Book b2("456", "Book B", "Author B", 2);
Book b3("789", "Book C", "Author C", 3);
tree.insert(b1);
tree.insert(b2);
tree.insert(b3);
cout << "In-order traversal of the tree:"<<endl;
tree.inorder();
string searchISBN = "456";
if (tree.search(searchISBN))
{
cout << "Book with ISBN " << searchISBN << " found."<<endl;
}
else
{
cout << "Book with ISBN " << searchISBN << " not found.\n";
}
tree.deleteValue("456");
cout<<"In-order traversal after deleting ISBN 456: "<<endl;
tree.inorder();
return 0;
}
Result:
The end!