Data Structures & Algorithms (CS-201) 2021
BSSE (3rd Semester)
Lab Report # 11
Introduction to Binary Tree
Section-B
SUMITTED TO
Sir Syed Ali Naqi Raza
SUMITTED BY
Armughan Ali (20-SE-039)
Samia Nawaz Yousafzai (20-SE-048)
Hooria Shahbaz (20-SE-042)
Department of Software Engineering
HITEC University, Taxila
Theory
Trees
Tree represents the nodes connected by edges. We will discuss binary tree or binary
search tree specifically. Binary Tree is a special data structure used for data storage
purposes. A binary tree has a special condition that each node can have a maximum
of two children. A binary tree has the benefits of both an ordered array and a linked
list as search is as quick as in a sorted array and insertion or deletion operation are as
fast as in linked list.
Task
Code
#include <iostream>
using namespace std;
struct Root {
int data;
Root* leftChild;
Root* rightChild;
};
class BinaryTree {
public:
Root* creatingTree() {
int data;
Root* temp = new Root;
cout << "\tEnter data: ";
cin >> data;
if (data == -1) {
return 0;
}
temp->data = data;
cout << "\n\tEnter left child of " << data << "\n";
temp->leftChild = creatingTree();
cout << "\n\tEnter right child of " << data << "\n";
temp->rightChild = creatingTree();
return temp;
}
void preorder(Root* root) {
if (root != NULL) {
cout << "\t" << root->data;
preorder(root->leftChild);
preorder(root->rightChild);
}
}
void inorder(Root* root) {
if (root != NULL) {
inorder(root->leftChild);
cout << "\t" << root->data;
inorder(root->rightChild);
}
}
void postorder(Root* root) {
if (root != NULL) {
postorder(root->leftChild);
postorder(root->rightChild);
cout << "\t" << root->data;
}
}
Root* minValueNode(Root* root) {
Root* current = root;
while (current && current->leftChild != NULL) {
current = current->leftChild;
}
return current;
}
Root* deleteNode(Root* root, int dataTodelete) {
if (root == NULL) {
return root;
}
if (root->data > dataTodelete) {
root->leftChild = deleteNode(root->leftChild, dataTodelete);
return root;
}
else if (root->data < dataTodelete) {
root->rightChild = deleteNode(root->rightChild, dataTodelete);
return root;
}
if (root->leftChild == NULL) {
Root* temp = root->rightChild;
delete root;
return temp;
}
else if (root->rightChild == NULL) {
Root* temp = root->leftChild;
delete root;
return temp;
}
else {
Root* succParent = root;
Root* succ = root->rightChild;
while (succ->leftChild != NULL) {
succParent = succ;
succ = succ->leftChild;
}
if (succParent != root) {
succParent->leftChild = succ->rightChild;
}
else {
succParent->rightChild = succ->rightChild;
}
root->data = succ->data;
delete succ;
return root;
}
}
};
int main() {
BinaryTree binaryTree;
Root *root = binaryTree.creatingTree();
cout << "\n\tPre Order :";
binaryTree.preorder(root);
cout << "\n\n";
cout << "\n\tIn Order :";
binaryTree.inorder(root);
cout << "\n\n";
cout << "\n\tPost Order : ";
binaryTree.postorder(root);
cout << endl;
cout << "\n\t\tDeleting\n";
cout << "\tEnter Value to Delete : "; int dataToDelete = 0; cin >> dataToDelete;
Root *newroot = binaryTree.deleteNode(root, dataToDelete);
cout << "\n\n";
cout << "\n\tPre Order :";
binaryTree.preorder(newroot);
cout << "\n\n";
return 0;
}
Output
Conclusion
In this lab, we grabbed the concept of the most powerful data structure and also put this
concept in to practical work by implementing its major functions that are insertion in a
binary tree, deletion in a binary tree, traversing a tree.
