Change the insert and _insert methods accordingly to comply with the new format. - If a new word is inserted that has a matching sorted order of its letters as an existing Node, do not insert a new Node. Instead, modify the existing Node and append the inserted word into the list. Starter Code class Node: def __init__(self, value): self.value = value self.left = None self.right = None def __str__(self): return ("Node({})".format(self.value)) __repr__ = __str__ class BinarySearchTree: ''' >>> x=BinarySearchTree() >>> x.insert('mom') >>> x.insert('omm') >>> x.insert('mmo') >>> x.root Node({'mmo': ['mom', 'omm', 'mmo']}) >>> x.insert('sat') >>> x.insert('kind') >>> x.insert('ats') >>> x.root.left Node({'ast': ['sat', 'ats']}) >>> x.root.right is None True >>> x.root.left.right Node({'dikn': ['kind']}) ''' def __init__(self): self.root = None # Modify the insert and _insert methods to allow the operations given in the PDF def insert(self, value): if self.root is None: self.root=Node(value) else: self._insert(self.root, value) def _insert(self, node, value): if(value
Change the insert and _insert methods accordingly to comply with the new format.
- If a new word is inserted that has a matching sorted order of its letters as an existing Node, do not insert a new Node. Instead, modify the existing Node and append the inserted word into the list.
Starter Code
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def __str__(self):
return ("Node({})".format(self.value))
__repr__ = __str__
class BinarySearchTree:
'''
>>> x=BinarySearchTree()
>>> x.insert('mom')
>>> x.insert('omm')
>>> x.insert('mmo')
>>> x.root
Node({'mmo': ['mom', 'omm', 'mmo']})
>>> x.insert('sat')
>>> x.insert('kind')
>>> x.insert('ats')
>>> x.root.left
Node({'ast': ['sat', 'ats']})
>>> x.root.right is None
True
>>> x.root.left.right
Node({'dikn': ['kind']})
'''
def __init__(self):
self.root = None
# Modify the insert and _insert methods to allow the operations given in the PDF
def insert(self, value):
if self.root is None:
self.root=Node(value)
else:
self._insert(self.root, value)
def _insert(self, node, value):
if(value<node.value):
if(node.left==None):
node.left = Node(value)
else:
self._insert(node.left, value)
else:
if(node.right==None):
node.right = Node(value)
else:
self._insert(node.right, value)
Modify the insert and _insert method
![Once all the changes are complete, you should be able to run the following lines of code and get
the following output:
>>> x=BinarySearchTree()
>> x.insert('mom')
>>> x.insert('omm')
>>> x.insert( 'mmo')
>>> x.root
Node ({ 'mmo': ['mom', 'omm', 'mmo']})
Modified functions
insert(self, value)
Inserts a word into the binary search tree. Words that have the same letter are saved together in a
list, in a dictionary. The key of the dictionary is the sorted order of all the letters in the word.
You will have to modify the _insert helper method as well.
Input
value Word to insert into the binary search tree
str](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F51f0269c-7668-4a31-8c7d-9938198c4dd9%2Fe789d4c2-24b9-4008-b62d-c26260a202d3%2Fz6guvc7_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
