//
// main.cpp
// Binary Search Tree [2]
//
// Created by Himanshu on 16/09/21.
//
#include <iostream>
using namespace std;
struct node {
int info = 0;
struct node *left, *right, *parent;
};
typedef struct node Node;
Node* createNode (int data, Node *par) {
Node* newNode = new node();
newNode->info = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = par;
return (newNode);
}
Node* insert (Node *root, int n, Node *par) {
if (root == NULL) {
root = createNode(n, par);
} else {
if (root->info > n) {
par = root;
root->left = insert (root->left, n, par);
} else {
par = root;
root->right = insert (root->right, n, par);
}
}
return root;
}
Node* search (Node *root, int n) {
if (root == NULL || root->info == n) {
return root;
} else {
if (root->info > n) {
return search (root->left, n);
} else {
return search (root->right, n);
}
}
}
Node* findMinimum (Node *root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
Node* findMaximum (Node *root) {
while (root->right != NULL) {
root = root->right;
}
return root;
}
Node* findSuccessor (Node *root) {
if (root->right != NULL) {
return findMinimum(root->right);
}
Node* y = root->parent;
while (y != NULL && root == y->right) {
root = y;
y = y->parent;
}
return y;
}
Node* deleteNode (Node *root, Node *x) {
Node *par = x->parent;
if (x->left != NULL && x->right != NULL) {
Node* z = findSuccessor(x);
x->info = z->info;
x = z;
}
par = x->parent;
if (x->left != NULL) {
if (par) {
if (par->left == x) {
par->left = x->left;
} else {
par->right = x->left;
}
} else {
root = par->left;
}
// To prevent memory leak
delete (x);
} else if (x->right != NULL) {
if (par) {
if (par->left == x) {
par->left = x->right;
} else {
par->right = x->right;
}
} else {
root = par->right;
}
// To prevent memory leak
delete (x);
} else {
if (par) {
if (par->left == x) {
par->left = NULL;
} else {
par->right = NULL;
}
} else {
root = NULL;
}
// To prevent memory leak
delete (x);
}
return root;
}
int main() {
Node *root = createNode(5, NULL);
root = insert(root, 3, NULL);
root = insert(root, 2, NULL);
root = insert(root, 4, NULL);
root = insert(root, 7, NULL);
//Searching 4 in the tree
if (search (root, 4)) {
cout<<"4 is present in the BST"<<endl;
} else {
cout<<"4 is not in the BST"<<endl;
}
//Searching parent of node 3 in the tree
Node *node = search (root, 3);
if (node->parent) {
cout<<"Parent of node 3 is "<<(node->parent->info)<<endl;
} else {
cout<<"Parent of node 3 is NULL"<<endl;
}
//Searching successor of node 2 in the tree
node = search (root, 2);
if (node) {
cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
} else {
cout<<"Successor of node 2 is NULL"<<endl;
}
//Deleting node 3 in the tree
cout<<"Deleting node 3"<<endl;
root = deleteNode(root, search (root, 3));
// Checking if node 3 exists in the tree
if (search (root, 3)) {
cout<<"3 is present in the BST"<<endl;
} else {
cout<<"3 is not in the BST"<<endl;
}
//Searching successor of node 2 in the tree
node = search (root, 2);
if (node) {
cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
} else {
cout<<"Successor of node 2 is NULL"<<endl;
}
//Searching successor of node 4 in the tree
node = search (root, 4);
if (node) {
cout<<"Successor of node 4 is "<<(findSuccessor(node)->info)<<endl;
} else {
cout<<"Successor of node 4 is NULL"<<endl;
}
return 0;
}