Need help please, would really apperciate it # The BST usually doesn\'t allow du

Question

Need help please, would really apperciate it

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

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

Explanation / Answer

if val == true :

return; // does not insert any data if

else

// your code for insertion goes here

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.