from collections import deque class Node: def __init__(self,key): self.data = key self.left = None self.right = None

class BST: def __init__(self): self.root = None

def insert(self,key):

    if self.root == None:
        self.root = Node(key)
        return 

    cur = self.root 

    while True:
        if cur.right != None and cur.data < key:
            cur = cur.right 
        elif cur.left != None and cur.data > key:
            cur = cur.left 
        else:
            break 

    if cur.data < key:
        cur.right = Node(key)
    else:
        cur.left = Node(key)

def delete(self,ref,value):
    if ref == None:
        return None 
    if not ref.left and not ref.right:
        if ref == self.root:
            self.root = None 
        return None 
    if value < ref.data:
        ref.left = self.delete(ref.left,value)
    elif value > ref.data:
        ref.right = self.delete(ref.right,value)
    else:
        ios = self.inOrderSuccessor(ref.right)
        ref.data = ios.data 
        ref.right = self.delete(ref.right,ios.data)
    return ref 

def inOrderSuccessor(self,cur):
    while cur and cur.left:
        cur = cur.left 
    return cur


def dfs(self,cur):
    if cur == None:
        return 
    self.dfs(cur.left)
    print(cur.data)
    self.dfs(cur.right)

def bfs(self):
    q = deque()
    q.append(self.root)

    while len(q):
        cur = q.popleft()
        print(cur.data)
        if cur.left != None:
            q.append(cur.left)
        if cur.right != None:
            q.append(cur.right)

obj = BST()

for i in range(10):

obj.insert(i+1)

obj.insert(5) obj.insert(2) obj.insert(3) obj.insert(4) obj.insert(7) obj.insert(6)

obj.dfs(obj.root) print() obj.bfs()

obj.delete(obj.root,2) print() obj.bfs()