BST Operations

Beginner

Another beginner problem on CodeChef based on concept of Binary Search Tree. If you are familiar with the concept, then you are ready to go, else, follow up the following concepts.

Binary Search Tree

Question

Or follow up the question from here

https://www.codechef.com/problems/BSTOPS

Analysis

1. We have to basically implement insert and delete operation in a binary search tree.
2. First line of input contains then number of times the user wants to perform operations on the binary search, say n.
3. And then n lines of operations. Each line containing two digits separated with a space. Like i 3 means insert 3 in the BST and d 3 means delete 3 in the Binary Search Tree.
4. All these operations should return the position where the operation has taken place.
5. Position is obtained as follows – 2*p for left and 2*p+1 for right node – where p is the root node that is 1.

All binary search tree operations that are insertion, searching, deletion and inorder printing has been explained here.

Binary Search Tree

Python Code

class _Node:
    def __init__(self, val, pos):
        self.val=val
        self.right=None
        self.left=None
        self.pos=pos

def min(val):
    current = val
    while current.left != None:
        current = current.left
    return current
    
        
def insert(node, val, pos):
    if node == None:
        print(pos)
        return _Node(val, pos)
    if val < node.val:
        node.left = insert(node.left, val, 2*pos)
    else:
        node.right = insert(node.right, val, 2*pos+1)
        
    return node
    

def delete(node, val):
    if node is None:
        return node
    if val < node.val:
        node.left = delete(node.left, val)
    elif val > node.val:
        node.right = delete(node.right, val)
    else:
        print(node.pos)
        if(node.left == None):
            temp = node.right
            node = None
            return temp
        elif(node.right == None):
            temp = node.left
            node = None
            return temp
        temp = min(node.right)
        node.val = temp.val
        node.right = delete(node.right,temp.val)
    return node



root = None 
for _ in range(int(input())):
    l=input().split()
    o=str(l[0])
    d=int(l[1])
    
    if(o == 'i'):
        root = insert(root, d, 1)
    elif(o == 'd'):
        root = delete(root,d)