BST Assignment
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
class Node {
int data;
Node* lptr;
Node* rptr;
Node(int val) : data(val), lptr(NULL), rptr(NULL) {}
friend class BST;
};
class BST {
private:
Node* root;
Node* InsertE(Node* node, int val) {
if (node == NULL)
return new Node(val);
if (node->data > val)
node->lptr = InsertE(node->lptr, val);
else
node->rptr = InsertE(node->rptr, val);
return node;
}
void DInorderE(Node* node) {
if (node != NULL) {
DInorderE(node->lptr);
cout << node->data << " ";
DInorderE(node->rptr);
}
}
void DPostE(Node* node) {
if (node != NULL) {
DPostE(node->lptr);
DPostE(node->rptr);
cout << node->data << " ";
}
}
void DPreE(Node* node) {
if (node != NULL) {
cout << node->data << " ";
DPreE(node->lptr);
DPreE(node->rptr);
}
}
void SearchIE(Node* node, int x) {
Node* temp = node;
while (temp != NULL) {
if (temp->data == x) {
cout << "Found " << x;
return;
}
if (temp->data > x) {
temp = temp->lptr;
} else {
temp = temp->rptr;
}
}
cout << "Not found " << x;
}
void SearchRE(Node* node, int x) {
if (node == NULL) {
cout << "Not found " << x;
return;
}
if (node->data == x) {
cout << "Found " << x;
return;
} else if (node->data > x) {
SearchRE(node->lptr, x);
} else {
SearchRE(node->rptr, x);
}
}
void InorderIterativeE(Node* node) {
stack<Node*> stk;
while (node != NULL || !stk.empty()) {
while (node != NULL) {
stk.push(node);
node = node->lptr;
}
node = stk.top();
stk.pop();
cout << node->data << " ";
node = node->rptr;
}
}
Node* deleteE(Node* node, int val) {
if (node == NULL) {
return node;
}
if (val < node->data) {
node->lptr = deleteE(node->lptr, val);
}
else if (val > node->data) {
node->rptr = deleteE(node->rptr, val);
}
else {
if (node->lptr == NULL) {
Node* temp = node->rptr;
delete node;
return temp;
}
else if (node->rptr == NULL) {
Node* temp = node->lptr;
delete node;
return temp;
}
Node* temp = node->rptr;
while (temp && temp->lptr != NULL) {
temp = temp->lptr;
}
node->data = temp->data;
node->rptr = deleteE(node->rptr, temp->data);
}
return node;
}
int heightRecE(Node *node){
if(node == NULL){
return 0;
}
int ht ,leftht ,rightht ;
leftht = heightRecE(node->lptr);
rightht = heightRecE(node->rptr);
if(leftht > rightht)
ht = leftht;
else
ht = rightht;
return ht+1;
}
void levelorderIterE(Node*node){
queue <Node* > q;
if(node==nullptr){
cout<<"empty tree";
}
q.push(node);
while(!q.empty()){
int size=q.size();
while(size>0){
node =q.front();
cout<<node->data<<" ";
q.pop();
if(node->lptr != NULL){
q.push(node->lptr);
}
if(node->rptr!= NULL){
q.push(node->rptr);
}
size--;
}
cout<<endl;
}
int findMinE(Node* node){
while (node->lptr != NULL) {
node = node->lptr;
}
cout<<"Min value in the tree :"<<node->data;
return node->data;
}
int findMaxE(Node* node){
while(node->rptr != NULL){
node = node->rptr;
}
cout<<"Max value in the tree :"<<node->data;
return node->data;
}
public:
BST() : root(NULL) {}
void Insert(int val) {
root = InsertE(root, val);
}
void DInorder() {
DInorderE(root);
}
void DPost() {
DPostE(root);
}
void DPre() {
DPreE(root);
}
void SearchI(int x) {
SearchIE(root, x);
}
void SearchR(int x) {
SearchRE(root, x);
}
void InorderIterative() {
InorderIterativeE(root);
}
void Delete(int val) {
root = deleteE(root, val);
}
void heightRec(){
cout<<"height of the tree is : "<< heightRecE(root);
}
void levelorderIter(){
levelorderIterE(root);
}
void findMin(){
findMinE(root);
}
void findMax(){
findMaxE(root);
}
};
int main() {
BST Bst;
int values[] = {8, 6, 10, 9, 11, 7, 17, 1};
int n = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < n; i++) {
Bst.Insert(values[i]);
}
cout << "Inorder traversal: ";
Bst.DInorder();
cout << endl;
cout << "Postorder traversal: ";
Bst.DPost();
cout << endl;
cout << "Preorder traversal: ";
Bst.DPre();
cout << endl;
cout<<endl;
cout <<"Searching of values :"<<endl;
Bst.SearchI(6);
cout << endl;
Bst.SearchR(12);
cout << endl;
cout<<endl;
cout << "Inorder Iterative: ";
Bst.InorderIterative();
cout << endl;
Bst.heightRec();
cout<<endl;
cout<<"Level order traversal :"<<endl;
Bst.levelorderIter();
cout<<endl;
Bst.Delete(9);
cout<<"Inorder Iterative after deletion :";
Bst.InorderIterative();
cout<<endl;
Bst.findMin();
cout<<endl;
Bst.findMax();
return 0;
}
OUTPUT:
PS C:\Users\Ruhan Tejwani\OneDrive\Desktop\c++ course> cd
"c:\Users\Ruhan Tejwani\OneDrive\Desktop\c++
course\.vscode\FDS\" ; if ($?) { g++ tree_submission.cpp -o
tree_submission } ; if ($?) { .\tree_submission }
Inorder traversal: 1 6 7 8 9 10 11 17
Postorder traversal: 1 7 6 9 17 11 10 8
Preorder traversal: 8 6 1 7 10 9 11 17
Searching of values :
Found 6
Not found 12
Inorder Iterative: 1 6 7 8 9 10 11 17
height of the tree is : 4
Level order traversal :
8
6 10
1 7 9 11
17
Inorder Iterative after deletion :1 6 7 8 10 11 17
Found 6
Not found 12
Inorder Iterative: 1 6 7 8 9 10 11 17
height of the tree is : 4
Level order traversal :
8
6 10
1 7 9 11
17
Inorder Iterative after deletion :1 6 7 8 10 11 17
Not found 12
Inorder Iterative: 1 6 7 8 9 10 11 17
height of the tree is : 4
Level order traversal :
8
6 10
1 7 9 11
17
Inorder Iterative after deletion :1 6 7 8 10 11 17
Level order traversal :
8
6 10
1 7 9 11
17
Inorder Iterative after deletion :1 6 7 8 10 11 17
6 10
1 7 9 11
17
Inorder Iterative after deletion :1 6 7 8 10 11 17
17
Inorder Iterative after deletion :1 6 7 8 10 11 17
Inorder Iterative after deletion :1 6 7 8 10 11 17
Inorder Iterative after deletion :1 6 7 8 10 11 17
Min value in the tree :1
Min value in the tree :1
Max value in the tree :17
PS C:\Users\Ruhan Tejwani\OneDrive\Desktop\c++
course\.vscode\FDS> cd "c:\Users\Ruhan
Tejwani\OneDrive\Desktop\c++ course\.vscode\FDS\" ; if ($?) { g++
tree_submission.cpp -o tree_submission } ; if ($?) { .\tree_submission
}
Inorder traversal: 1 6 7 8 9 10 11 17
Postorder traversal: 1 7 6 9 17 11 10 8
Preorder traversal: 8 6 1 7 10 9 11 17
Searching of values :
Found 6
Not found 12
Inorder Iterative: 1 6 7 8 9 10 11 17
height of the tree is : 4
Level order traversal :
8
6 10
1 7 9 11
17
Inorder Iterative after deletion :1 6 7 8 10 11 17
Min value in the tree :1
Max value in the tree :17
