Them va xoa 1 phan tu trong cay nhi phan (BST)

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

Test data

• 1 ≤ N ≤ 10³
• -10⁹ ≤ x ≤ 10⁹
• 1 ≤ position(x) ≤ 2³² - 1
• It is guaranteed that there will be no duplicates in the BST

Sample Input

5
i 1
i 2
i 0
d 2
i 3
 

Sample Output

1
3
2
3
3
 

Explanation

On inserting 1,

1

On inserting 2:

1
 \
  2

On inserting 0:

   1
  / \
 0   2

After deleting 2:

  1
 /
0

On inserting 3:

   1
  / \
 0   3

 /*****************/

#include <iostream>
using namespace std;
typedef long long ll;


struct node{
    
    ll data, pos;
    struct node *left, *right;
};

node *insert(node *root, ll data, ll pos);
node *deletenode(node *root, ll data);
node *findMax(node *);
node *findMin(node *);
void inorder(node *);
int main() {
 ll q,num;
 char op;
 
 node *root = NULL;

    // root = insert(root, 1, 1);
    // root = insert(root, 2, 1);
    // root = insert(root, 3, 1);
    // root = insert(root, 4, 1);
    // //inorder(root);
    // root = deletenode(root,4);
    //cout<<endl;
    //inorder(root);
    cin>>q;

 while(q-->0){
         
        cin>>op>>num;
        if(op=='i')
           root = insert(root,num,1);
         else
             root = deletenode(root,num);
  }
 
 return 0;
}


node* insert(node *root, ll data, ll pos){

    if(!root){
        cout<<pos<<endl;
        root = new node;
        root->data = data;
        root->pos = pos;
        root->left = root->right = NULL;
        return root;        
    }
    else{
        if(data > root->data){

            root->right = insert(root->right, data, 2*pos+1);
        }
        else{

            root->left = insert(root->left, data, 2*pos);
        }
    }
    
    return root;
}


node* deletenode(node *root, ll data){

 if(!root)
  return root;
 if(root->data >  data){

  root->left = deletenode(root->left, data);
 }
 else if(data > root->data){

  root->right = deletenode(root->right, data);
 }
 else{
        
        cout<<root->pos<<endl;
  if(root->left && root->right){
   node *temp = findMin(root->right);
   root->data = temp->data;
   root->right = deletenode(root->right, temp->data);
  }
  else{
            
   node *temp;
   if(root->left){

    temp = root->left;
       delete root;
       return temp;
   }
   else if(root->right){

    temp =root->right;
    delete root;
    return temp;
   }
   else{
    
    temp = root;
    delete temp;
    return NULL;
   }
   
   
  }

 }


return root; 
 
}




node *findMax(node *root){
    while(root->right)   
    root = root->right;
    return root;
}

void inorder(node *root){

    if(root){

        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);

    }
}

node *findMin(node *root){
    while(root->left)   
    root = root->left;
    return root;
}