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.
Or follow up the question from here
- We have to basically implement insert and delete operation in a binary search tree.
- First line of input contains then number of times the user wants to perform operations on the binary search, say n.
- 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.
- All these operations should return the position where the operation has taken place.
- 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.
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) d=int(l) if(o == 'i'): root = insert(root, d, 1) elif(o == 'd'): root = delete(root,d)