In this problem successful submissions are printing more than required
for case when root has two child
Whereas My code is Printing Exactly what is required.There might be flaw in test cases.
#include
using namespace std;
struct BstNode
{
long long int data;
int pos;
BstNode* left;
BstNode* right;
};
//Pointer to root not root itself
BstNode* GetNewNode(long long int data,int pos)
{
BstNode* newNode = new BstNode;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->pos = pos;
cout<pos;
return newNode;
}
BstNode* Insert(BstNode* rootPtr,long long int data,int pos =1)
{
if(rootPtr == NULL)
{
rootPtr = GetNewNode(data,pos);
}
else if( data <= rootPtr->data)
{
rootPtr->left = Insert(rootPtr->left,data,2*pos);
}
else
{
rootPtr->right = Insert(rootPtr->right,data,2*pos+1);
}
return rootPtr;
}
BstNode* FindMin(BstNode* root)
{
while(root != NULL && root->left != NULL )
{
root = root->left;
}
return root;
}
BstNode* Delete(BstNode* root,long long int data)
{
if(root == NULL)
{
return root;
}
else if(data < root->data) root->left = Delete(root->left,data);//Delete function will return the address of modified left subtree.
else if(data > root->data) root->right = Delete(root->right,data);
else // Wohoo…I found you,Get ready to be deleted
{ cout<pos;
//Case 1: No child
if(root->left == NULL && root->right == NULL)
{
// cout<pos;
delete root;
root = NULL;
}
//Case 2: One child
else if(root->left == NULL)
{
BstNode* temp = root;
root= root->right;
// cout<<temp->pos;
delete temp;
}
else if(root->right == NULL)
{
BstNode* temp = root;
root= root->left;
// cout<<temp->pos;
delete temp;
}
//Case 3: Two children
else {
BstNode* temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right,temp->data);
}
}
return root;
}
long long int Pos(BstNode* rootPtr,long long int data,long long int pos =1)
{
if(rootPtr == NULL)
return pos-1 ;
else if(rootPtr->data == data)
return pos;
else if(data <= rootPtr->data)
{ pos = 2*pos;
return Pos(rootPtr->left,data,pos);
}
else
{ pos = 2*pos+1;
return Pos(rootPtr->right,data,pos);
}
}
int main()
{ BstNode* rootPtr;
rootPtr = NULL;
long long int Q,x;
char r;
cin>>Q;
while(Q != 0)
{
cin>>r>>x;
if(r=='i')
{
rootPtr = Insert(rootPtr,x);
// cout<<Pos(rootPtr,x)<<"\n";
}
else
// { cout<<Pos(rootPtr,x)<<"\n";
rootPtr = Delete(rootPtr,x);
Q--;
}
// cout<<"Enter number be searched \n";
// cin>>number;
// if(Search(rootPtr,number) == true ) cout<<"Found\n";
// else cout<<"Not Found\n";
return 0;
}