BST Operations Codechef Solution

Hello Programmers In this post, you will know how to solve the BST Operations Codechef Solution.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for 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:

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

report this ad

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