# BST Operations

CodeChef Beginner Question Analysis/Solution

0
1

#### 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)

``````

SHARE