'''
inorder()function time complexity : O(n)
insert() function time complexity : O(n)
delete() function time complexity : O(n)
'''
class Node:
def __init__(self, key):
self.val = key
self.left = None
self.right = None
def inorder(root):
if root is not None:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
def insert(root, key):
if root is None:
return Node(key)
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
def minValueNode(root):
while root.left is not None:
root = root.left
return root
def deleteNode(root, key):
if root is None:
return root
if root.val > key:
root.left = deleteNode(root.left, key)
elif root.val < key:
root.right = deleteNode(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = minValueNode(root.right)
root.val = temp.val
root.right = deleteNode(root.right, temp.val)
return root
if __name__ == '__main__':
""" Let us create following BST
50
/
30 70
/ /
20 40 60 80
/
55
inorder traversal->[20, 30, 40, 50, 55, 60, 70, 80]
"""
root = None
root = insert(root, 80)
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 55)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
print("Inorder traversal of the given tree")
inorder(root)
print("
Delete->50")
root = deleteNode(root, 50)
print("Inorder traversal of the modified tree")
inorder(root)
print("
Delete->20")
root = deleteNode(root, 20)
print("Inorder traversal of the modified tree")
inorder(root)
print("
Delete->30")
root = deleteNode(root, 70)
print("Inorder traversal of the modified tree")
inorder(root)