BST Operations Codechef Solution

BST Operations Codechef Solution: Hello coders, today we are going to solve BST Operations Codechef Solution.

Problem

Perform QQ operations of the form:

ii xx : Insert xx in the BST.
dd xx : Delete xx from the BST.

Each element is assigned a value based on its position when it was inserted into the BST. The position of an element is calculated as follows:

• The position of the root node is 11.
• If the position of a node is pp, the positions of its left and right children are (2∗p2∗p) and (2∗p+12∗p+1), respectively.

Note that the positions of the elements may change after some operations, but their values don’t.

For each of the QQ queries, output the value that is associated with that element in the BST. It is guaranteed that there will be no duplicates in the BST, and a delete operation on an element shall only be called if it’s present in the BST.

INPUT:

• The first line contains QQ, the number of operations to be performed.
• Each of the next QQ lines contain either ii xx or dd xx, as described above.

OUTPUT:

For each query, print the value associated with this element after it was inserted into, or before it was deleted from the BST, based on the query.

CONSTRAINTS:

• 1≤Q≤1031≤Q≤103
• −109≤x≤109−109≤x≤109
• 1≤1≤ position(xx) ≤232−1≤232−1
• It is guaranteed that there will be no duplicates in the BST.
• A delete operation on an element will only be called if it’s present in the BST.

```5
i 1
i 2
i 0
d 2
i 3
```

```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
/
On inserting 3:
1
/ \
0   3```

Broken Telephone CodeChef Solution in JAVA

```import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import static java.lang.Math.min;
import static java.lang.Math.max;
class UTS1 {
private static InputReader in;
private static PrintWriter out;
static long max(long a, long b){
if(a > b)
return a;
return b;
}
static long min(long a, long b){
if(a < b)
return a;
return b;
}
static class Node{
public long data,pos;
public Node left,right;
public Node(long data, long pos) {
this.data = data;
this.pos = pos;
}
}
static Node Insert(Node root, long data, long pos){
if(root == null){
out.println(pos);
return (new Node(data,pos));
}
if(data<root.data)
root.left= Insert(root.left,data,(2*pos));
else if(data> root.data)
root.right = Insert(root.right,data,(2*pos+1));
return root;
}
static Node Delete(Node root, long data, boolean pr){
if(root == null)
return root;
if(data<root.data)
root.left = Delete(root.left,data,pr);
else if(data> root.data)
root.right = Delete(root.right, data,pr );
else {
if(pr)
out.println(root.pos);
if(root.left==null && root.right==null)
root = null;
else if(root.left==null)
root = root.right;
else if(root.right==null)
root = root.left;
else{
Node temp = minValue(root.right);
root.data = temp.data;
root.right = Delete(root.right,temp.data,false);
}
}
return root;
}
public static Node minValue(Node root)
{
Node current = root;
while(current.left!=null)
{
current = current.left;
}
return current;
}
static void solve(){
int N = in.nextInt();
Node root= null;
for(int i = 0 ; i < N ; i ++){
String t = in.next();
long data = in.nextInt();
if(t.charAt(0)=='i')
{
root = Insert(root,data,1);
}
else
{
root = Delete(root,data,true);
}
}BST Operations
}
public static void main(String args[]) throws IOException {
InputStream inputStream = System.in;
in = new InputReader(inputStream);
OutputStream outputStream = System.out;
out = new PrintWriter(outputStream);
solve();
out.flush();
}
static class InputReader {
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}BST Operations ```

BST Operations CodeChef Solution in CPP

```#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node *left, *right;
int pos;
Node (int v, int pos) {
val = v;
left = NULL;
right = NULL;
this->pos = pos;
}
};
Node *insert(Node *root, int n, int pos) {
if (root == NULL) {
cout << pos << '\n';
root = new Node(n, pos);
return root;
}
if (n <= root->val) {
root->left = insert(root->left, n, 2 * pos);
} else {
root->right = insert(root->right, n, 2 * pos + 1);
}
return root;
}
Node *deleteOperation(Node *root, int n, bool check) {
if (root == NULL) {
return root;
} else if (n < root->val) {
root->left = deleteOperation(root->left, n, check);
return root;
} else if (n == root->val) {
if (check) {
cout << root->pos << '\n';
}
if (root->left == NULL && root->right == NULL) {
delete root;
return NULL;
} else if (root->left && root->right == NULL) {
Node *temp = root->left;
delete root;
return temp;
} else if (root->left == NULL && root->right) {
Node *temp = root->right;
delete root;
return temp;
}
Node *replace = root->right;
while (replace->left != NULL) {
replace = replace->left;
}
root->val = replace->val;
root->right = deleteOperation(root->right, replace->val, false);
return root;
} else {
root->right = deleteOperation(root->right, n, check);
return root;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Node *root = NULL;
int tt;
cin >> tt;
while (tt--) {
char ch;
int n;
cin >> ch >> n;
if (ch == 'i') {
root = insert(root, n, 1);
} else {
root = deleteOperation(root, n, true);
}
}
return 0;
}
```

BST Operations CodeChef Solution in Python

```class Node():
def __init__(self,val,pos):
self.right = None
self.left = None
self.pos = pos
self.key = val
def insert(root,key,pos):
if root == None:
root = Node(key,pos)
print(pos)
elif(root.key > key):
root.left = insert(root.left,key,pos =(pos * 2))
elif (root.key < key):
root.right = insert(root.right,key,pos =((pos * 2)+1))
return root
def minValueNode(node):
current = node
while (current.left is not None):current = current.left
return current
def delete(root,key,prt= True):
if root is None:
return
elif (root.key < key):
root.right = delete(root.right,key,prt)
elif root.key > key:
root.left = delete(root.left,key,prt)
else:
if prt:
print(root.pos)
if root.left is None and root.right is None:
root = None
elif root.right is None:
root = root.left
elif root.left is None:
root = root.right
else:
temp = minValueNode(root.right)
root.key = temp.key
root.right = delete(root.right,temp.key,prt= False)
return root
root = None
for i in range(int(input())):
op, key = input().split()
key = int(key)
if op == 'i':
root =insert(root,key,1)
else:
root= delete(root,key)
```

Disclaimer: The above Problem (BST Operations) is generated by CodeChef but the solution is provided by Chase2learn. This tutorial is only for Educational and Learning purpose.

Sharing Is Caring