BST Operations Codechef Solution

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

Codechef solutions

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.

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

Broken Telephone – CodeChef Solution in JAVA

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
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 BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        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.

Leave a Comment