MIZAN TEPI UNIVERSITY
SCHOOL OF COMPUTING AND INFORMATICS
DEPARTMENT OF COMPUTER SCIENCE
PROGRAM WEEKEND YEAR 3 TERM 1
COURSE TITLE:- DATA STRUCTURES ALGORITHMS
GROUP ONE ASSIGNMENT
Student Name ID No
1. Yohannes Bheru ------------------------------- scie/042/13
2. Ashagera Lewi ------------------------------- scie/ 004/13
3. Mikael Gemechu ------------------------------- scie/023/13
4. Lideya Belachew --------------------- ---------scie/020/13
5. Asefa Ketema ---------------------- --------scie/0 07/13
6. Petros Shiferaw ------------------------------- scie/028 /13
7. Fikadu Shaz ------------------------------- scie/014/13
1.Write a program to perform the following operations:
a) Insert an element into a binary search tree.
b) Delete an element from a binary search tree.
c) Search for a key element in a binary search tree.
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node* left;
Node* right;
Node(int key) {
this->key = key;
left = nullptr;
right = nullptr;
}
};
Node* insert(Node* root, int key) {
if (root == nullptr) {
return new Node(key);
} else {
if (key < root->key) {
root->left = insert(root->left, key);
} else {
root->right = insert(root->right, key);
}
}
return root;
}
Node* findMin(Node* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
Node* deleteNode(Node* root, int key) {
if (root == nullptr) {
return root;
}
if (key < root->key) {
root->left = deleteNode(root->left, key);
} else if (key > root->key) {
root->right = deleteNode(root->right, key);
} else {
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
}
Node* successor = findMin(root->right);
root->key = successor->key;
root->right = deleteNode(root->right, successor->key);
}
return root;
}
Node* search(Node* root, int key) {
if (root == nullptr || root->key == key) {
return root;
}
if (key < root->key) {
return search(root->left, key);
}
return search(root->right, key);
}
void inorderTraversal(Node* root) {
if (root != nullptr) {
inorderTraversal(root->left);
cout << root->key << " ";
inorderTraversal(root->right);
}
}
int main() {
Node* root = nullptr;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
cout << "Inorder traversal of the binary search tree:" << endl;
inorderTraversal(root);
int keyToDelete = 30;
root = deleteNode(root, keyToDelete);
cout << "\n\nAfter deleting " << keyToDelete << " from the binary search tree:" << endl;
inorderTraversal(root);
int keyToSearch = 60;
Node* result = search(root, keyToSearch);
if (result) {
cout << "\n\nKey " << keyToSearch << " found in the binary search tree." << endl;
} else {
cout << "\n\nKey " << keyToSearch << " not found in the binary search tree." << endl;
}
return 0;
}
