# The BST usually doesn't allow duplicated items. hw9.py produces a wrong BST.

# Modify our implementation of the binary search tree so that it handles duplicate keys properly.

# That is, if a key is already in the tree then the new payload should replace the old rather than add another node with the same key.

# correct BST

# 10

# / \

# 6 14

# / \ /\

#4 8 12 16

# with current implementation, the BST is

# 10

# / \

# 6 14

# / \ /\

#4 8 12 16

# \

# 6

# modify the insert function to create a correct BST

class Node:

def __init__(self, val):

self.left = None # pointer to the left subtree

self.right = None # pointer to the right subtree

self.data = val # key (node value)

class BST:

def __init__(self,data): # Binary Search Tree init

self.root = Node(data)

#############

############# DO NOT MODIFY ABOVE THIS LINE : 0 POINT IF YOU DO SO ##########

def insert(self,data,node=None):

if node is None: # need it to start the recursive function

node = self.root

if data > node.data: # if the value to be inserted is > node value

if node.right is None:

node.right = Node(data)

else:

self.insert(data,node.right)

else:

if node.left is None:

node.left = Node(data)

else:

self.insert(data,node.left)

def search(self,node,val):

if node is None :

return False

elif (val == node.data):

return True

elif (val < node.data):

return self.search(node.left, val)

else:

return self.search(node.right, val)

def delete(self, key):

self.root, deleted = self._delete_value(self.root, key)

return deleted

def _delete_value(self, node, key):

if node is None:

return node, False

deleted = False

if key == node.data:

deleted = True

if node.left and node.right: # 2 children

# replace the node to the smallest node of the right subtree

parent, child = node, node.right

while child.left is not None:

parent, child = child, child.left

child.left = node.left

if parent != node:

parent.left = child.right

child.right = node.right

node = child

elif node.left or node.right: # 0 or 1 child

node = node.left or node.right

else:

node = None

elif key < node.data:

node.left, deleted = self._delete_value(node.left, key)

else:

node.right, deleted = self._delete_value(node.right, key)

return node, deleted

############# DO NOT MODIFY BELOW THIS LINE : 0 POINT IF YOU DO SO ##########

#############

def levelorderwithLevelInfo(self,root):

queue = [root]

while queue != []:

level_node = len(queue)

while level_node > 0:

node = queue.pop(0)

if node.left: queue.append(node.left)

if node.right: queue.append(node.right)

print(node.data, end = " ")

level_node -= 1

print("")

if __name__=='__main__':

bst = BST(10)

bst.insert(6)

bst.insert(14)

bst.insert(4)

bst.insert(8)

bst.insert(12)

bst.insert(16)

bst.insert(6) #<-------- adding 6 again

print('6 should not be added twice - it is a wrong BST ')

bst.levelorderwithLevelInfo(bst.root)