Assignment description:

Inthisexercise,youaregivenanimplementationofabinarysearchtree.

Theclass``BST``,foundintheexercisepackage,containsthemethods

``insert``and``find``whichcanbeusedforinsertingandfindingkey-value

pairs.

Thesemethodsutilizetworecursivehelpermethods``_inserthelp``and

``_findhelp``toworkproperly.

Yourtaskistoimplementthesehelpermethods.

Inaddition,youshouldimplementthemethod``_visit_inorder``whichreturns

aniteratoryieldingthenodesofthetreeininorder.

Youdonotneedtochangethecodeoutsidethese3methodstogetfull

points.

'''

Problem:

Can't figure out the how to do _inserthelp function, everything else seems to be working pretty well... It currently does not work, but I'm pretty sure I'm close. The current function can add the first node (the root) and also the second node, which would be root.left. After that it doesn't work.

The code:

classBSTNode:

"""

Representsnodesinabinarysearchtree.

"""

def__init__(self,key,value=None):

self.key=key

self.value=value

self.left=None

self.right=None

defheight(self):

"""Returntheheightofthisnode."""

left_height=1+self.left.height()ifself.leftelse0

right_height=1+self.right.height()ifself.rightelse0

returnmax(left_height,right_height)

def__repr__(self):

return"".format(self.key,self.value,id(self))

classBSTException(Exception):

pass

classBST:

"""

Simplerecursivebinarysearchtreeimplementation.

"""

def__init__(self,NodeClass=BSTNode):

self.BSTNode=NodeClass

self.root=None

self.nodes=0

#Updatedaftereachcalltoinsert

self.newest_node=None

deffind(self,find_key):

"""Returnnodewithkeyfind_keyifitexists.Ifnot,returnNone."""

returnself._findhelp(self.root,find_key)

definsert(self,new_key,value=None):

"""Insertanewnodewithkeynew_keyintothisBST,

increasenodecountbyoneandreturntheinsertednode."""

ifself.find(new_key)isnotNone:

raiseKeyError("ThisBSTalreadycontainskey{0!r}".format(new_key))

ifself.root==None:

self.root=self._inserthelp(self.root,new_key,value)

self.newest_node=self.root

else:

self.newest_node=self._inserthelp(self.newest_node,new_key,value)

self.nodes+=1

returnself.newest_node

defheight(self):

"""Returntheheightofthistree."""

returnself.root.height()ifself.rootelse-1

def__iter__(self):

"""Returnaniteratorofthekeysofthistreeinsortedorder."""

fornodeinself._visit_inorder(self.root):

yieldnode.key

def__len__(self):

returnself.nodes

#Implementthemethodsbelow.

def_findhelp(self,node,find_key):

"""Startingfromnode,searchfornodewithkeyfind_keyandreturnthatnode.

Ifnonodewithkeyfind_keyexists,returnNone."""

inorderlist=self._visit_inorder(node)

for_nodeininorderlist:

if_nodeisNoneorfind_key==_node.key:

return_node

#Endsearch

returnNone

#Implementfunctionalitytorecursivelychoosethenextnode

def_inserthelp(self,node,new_key,value):

"""Startingfromnode,findanemptyspotforthenewnodeand

insertitintothisBST."""

ifnodeisNone:

self.newest_node=BSTNode(new_key,value)

else:

#Dolevelordertraversaluntilwefind

#anemptyplace.

if(notnode.left):

node.left=BSTNode(new_key,value)

self.newest_node=BSTNode(new_key,value)

break

else:

tree.append(node.left)

if(notnode.right):

node.right=BSTNode(new_key,value)

self.newest_node=BSTNode(new_key,value)

break

else:

tree.append(node.right)

returnself.newest_node

def_visit_inorder(self,starting_node):

definorder(node,indorderlist):

ifnodeisNone:

return

else:

inorder(node.left,inorderlist)

indorderlist.append(node)

inorder(node.right,inorderlist)

inorderlist=[]

inorder(starting_node,inorderlist)

returninorderlist