I was solving a problem and it stated:
Write a program that processes the following queries on a Binary Search Tree:
- i x: Insert x in the BST
- d x: Delete x from the BST
Input format
Line 1 contains an integer Q, the number of queries
The next Q lines are of the form i x or d x
Output format
For each query, print the position of x in the BST
If the position of a node is p, the positions of its left and right children are 2*p and 2*p+1 respectively
Position of the root node is 1
11 //Queries
i 15 //i=insert; d=delete
i 9
i 25
i 8
i 13
i 18
i 19
i 7
i 11
d 9
i 14
Everything is working fine until I delete node 9. then the position of node 14 is coming out to be 5. see the diagram:Initially,
15
/ \
9 25
/ \ /
8 13 18
/ / \
7 11 19
After deleting 9;
15
/ \
11 25
/ \ /
8 13 18
/ \
7 19
After inserting 14
15
/ \
11 25
/ \ /
8 14 18
/ / \
7 13 19
Correct format should be
15
/ \
11 25
/ \ /
8 13 18
/ \ \
7 14 19
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll position=1;
struct BSTNode
{
int data;
BSTNode *left,*right;
};
BSTNode *getNewNode(int data)
{
BSTNode *newNode = new BSTNode();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode; //returns address of new node
}
BSTNode* insert(BSTNode *root,int data)
{
if(root==NULL){
root = getNewNode(data);
}
else if(data<root->data)
{
root->left = insert(root->left,data);
}
else if(data>root->data)
{
root->right = insert(root->right,data);
}
return root;
}
BSTNode *findMin(BSTNode *root)
{
if(root->left ==NULL)
{
return root;
}
else
findMin(root->left);
}
bool search(BSTNode *root,int data)
{
if(root == NULL)
{
return 0;
}
if(data<root->data)
{
position=2*position;
search(root->left,data);
}
else if(data>root->data)
{
position=2*position+1;
search(root->right,data);
}
else
{
cout<<"Found";
return 1;
}
}
BSTNode* delet(BSTNode* root,int data)
{
if(root == NULL)
{
return 0;
}
else if(data<root->data)
{
root->left = delet(root->left,data);
}
else if(data>root->data)
{
root->right = delet(root->right,data);
}
else //Found
{
//CASE 1:No child
if(root->left == root->right ==NULL)
{
delete root;
root = NULL;
}
//CASE2: One child
else if(root->left == NULL)
{
BSTNode *temp= root;
root = root->right;
delete temp;
}
else if(root->right == NULL)
{
BSTNode *temp=root;
root= root->left;
delete temp;
}
//CASE 3: TWO CHILD
else
{
BSTNode *temp = findMin(root->right);
root->data = temp->data;
root->right = delet(root->right,root->data);
}
return root;
}
}
int main()
{
BSTNode* root = NULL; //rootptr- pointer to node
//tree is empty
int n,input,data,del;
char c;
cin>>n;
while(n--)
{
cin>>c;
cin>>input;
if(c=='i')
{
root = insert(root,input);
search(root,input);
}
if(c=='d')
{
search(root,input);
delet(root,input);
}
cout<<position<<endl;
position=1;
}
return 0;
}
How is this possible insertion is being done as a leaf node Then?
