bst with parent pointer
#include<iostream>
#include<queue>
using namespace std;
struct Node {
int data;
Node *left, *right, *parent;
};
struct Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = temp->parent = NULL;
return temp;
}
void inorderTraverse(struct Node *root) {
if (root != NULL) {
// Traverse left
inorderTraverse(root->left);
// Traverse root
printf("%d -> ", root->data);
// Traverse right
inorderTraverse(root->right);
}
}
struct Node* insert(struct Node* node, int key) {
if (node == NULL) return newNode(key);
if (key < node->data) { //to the left subtree
Node *left_child = insert(node->left, key);
node->left = left_child;
left_child->parent = node;
}
else if (key > node->data) { // to the right subtree
Node *right_child = insert(node->right, key);
node->right = right_child;
right_child->parent = node;
}
return node;
}
/* deletion function */
void deleteNode(Node *root, int data)
{
if(root == NULL){
cout << "Tree is empty\n";
return;
}
queue<Node*> q;
q.push(root);
while(!q.empty()){
Node *temp = q.front();
q.pop();
if(temp->data == data){
Node *current = root;
Node *prev;
while(current->right != NULL){
prev = current;
current = current->right;
}
temp->data = current->data;
prev->right = NULL;
free(current);
cout << "Deleted\n";
return;
}
if(temp->left != NULL)
q.push(temp->left);
if(temp->right != NULL)
q.push(temp->right);
}
}
int main() {
struct Node *root = NULL;
root = insert(root, 100);
insert(root, 60);
insert(root, 40);
insert(root, 80);
insert(root, 140);
insert(root, 120);
insert(root, 160);
inorderTraverse(root); cout << endl;
deleteNode(root, 140);
deleteNode(root, 60);
deleteNode(root, 140);
inorderTraverse(root); cout << endl;
}