I am trying to delete and replace a node with the deepest node but my program only removes the node.
I studied a code i found on internet and copied the code but i am getting a different output than the original program.
original output:
Inorder traversal before deletion : 7 11 12 10 15 9 8
Inorder traversal after deletion : 7 8 12 10 15 9
my program:
Inorder traversal before deletion : 7 11 12 10 15 9 8
Inorder traversal after deletion : 7 12 10 15 9 8
I need help in understanding why it is so? and how to fix it?.
original program -> https://www.geeksforgeeks.org/deletion-binary-tree/
my program
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int key)
{
struct Node* temp= new Node;
temp->key=key;
temp->left=temp->right=NULL;
return temp;
}
void inorder(struct Node* temp)
{
if(!temp)
return;
inorder(temp->left);
cout<<temp->key<<" ";
inorder(temp->right);
}
void deletDeepest(struct Node* root,struct Node* d_node)
{
queue <struct Node*> q;
q.push(root);
struct Node* temp;
while(!q.empty())
{
temp = q.front();
q.pop();
if(temp==d_node)
{
temp=NULL;
delete(d_node);
return;
}
if(temp->right)
{
if(temp->right==d_node)
{
temp->right=NULL;
delete(d_node);
return;
}
else
q.push(temp->right);
}
if(temp->left)
{
if(temp->left==d_node)
{
temp->left=NULL;
delete(d_node);
return;
}
else
q.push(temp->left);
}
}
}
void deletion(struct Node* root, int key)
{
struct Node* temp;
struct Node* key_node=NULL;
queue <struct Node*> q;
q.push(root);
while(!q.empty())
{
temp=q.front();
q.pop();
if(temp->key==key)
key_node=temp;
if(temp->right)
q.push(temp->right);
if(temp->left)
q.push(temp->left);
}
int x = temp->key;
deletDeepest(root,temp);
key_node->key=x;
}
int main()
{
struct Node* root = newNode(10);
root->left = newNode(11);
root->left->left = newNode(7);
root->left->right = newNode(12);
root->right = newNode(9);
root->right->left = newNode(15);
root->right->right = newNode(8);
cout << "Inorder traversal before deletion : ";
inorder(root);
int key = 11;
deletion(root, key);
cout << endl;
cout << "Inorder traversal after deletion : ";
inorder(root);
return 0;
}
