Write and test a recursive version of the find function in BST class, write preorder and postorder traversal generators for the BST class. Example to generate a preorder traversal we write code like list(myBST.preorder()). And add a __len__ operation to BST class such that calling len(myBST) shoud return the number of items. In python please. The code needed is below and what i want to do is what i asked above about the find function and the rest.

class TreeNode(object):

def __init__(self, data = None, left=None, right=None):

“””creates a tree node with specified data and references to left

and right children”””

self.item = data

self.left = left

self.right = right

from TreeNode import TreeNode

class BST:

#————————————————————

def __init__(self):

“””create empty binary search tree

post: empty tree created”””

self.root = None

#————————————————————

def insert(self, item):

“””insert item into binary search tree

pre: item is not in self

post: item has been added to self”””

if self.root is None: # handle empty tree case

self.root = TreeNode(item)

else:

# start at root

node = self.root

# loop to find the correct spot (break to exit)

while True:

if item == node.item:

raise ValueError(“Inserting duplicate item”)

if item < node.item: # item goes in left subtree

if node.left is not None: # follow existing subtree

node = node.left

else: # empty subtree, insert here

node.left = TreeNode(item)

break

else: # item goes in right subtree

if node.right is not None: # follow existing subtree

node = node.right

else: # empty subtree, insert here

node.right = TreeNode(item)

break

#————————————————————

def insert_rec(self, item):

“””insert item into binary search tree

pre: item is not in self

post: item has been added to self”””

self.root = self._subtreeInsert(self.root, item)

#————————————————————

def _subtreeInsert(self, root, item):

if root is None: # inserting into empty tree

return TreeNode(item) # the item becomes the new tree root

if item == root.item:

raise ValueError(“Inserting duplicate item”)

if item < root.item: # modify left subtree

root.left = self._subtreeInsert(root.left, item)

else: # modify right subtree

root.right = self._subtreeInsert(root.right, item)

return root # original root is root of modified tree

#————————————————————

def find(self, item):

“”” Search for item in BST

post: Returns item from BST if found, None otherwise”””

node = self.root

while node is not None and not(node.item == item):

if item < node.item:

node = node.left

else:

node = node.right

if node is None:

return None

else:

return node.item

#————————————————————

def delete(self, item):

“””remove item from binary search tree

post: item is removed from the tree”””

self.root = self._subtreeDelete(self.root, item)

#————————————————————

def _subtreeDelete(self, root, item):

if root is None: # Empty tree, nothing to do

return None

if item < root.item: # modify left

root.left = self._subtreeDelete(root.left, item)

elif item > root.item: # modify right

root.right = self._subtreeDelete(root.right, item)

else: # delete root

if root.left is None: # promote right subtree

root = root.right

elif root.right is None: # promote left subtree

root = root.left

else:

# root node can’t be deleted, overwrite it with max of

# left subtree and delete max node from the subtree

root.item, root.left = self._subtreeDelMax(root.left)

return root

#————————————————————

def _subtreeDelMax(self, root):

if root.right is None: # root is the max

return root.item, root.left # return max and promote left subtree

else:

# max is in right subtree, recursively find and delete it

maxVal, root.right = self._subtreeDelMax(root.right)

return maxVal, root

#————————————————————

def asList(self):

“””gets item in in-order traversal order

post: returns list of items in tree in orders”””

items = []

self._subtreeAddItems(self.root, items)

return items

#————————————————————

def _subtreeAddItems(self, root, itemList):

if root is not None:

self._subtreeAddItems(root.left, itemList)

itemList.append(root.item)

self._subtreeAddItems(root.right, itemList)

#————————————————————

def visit(self, f):

“””perform an in-order traversal of the tree

post: calls f with each TreeNode item in an in-order traversal

order”””

self._inorderVisit(self.root, f)

#————————————————————

def _inorderVisit(self, root, f):

if root is not None:

self._inorderVisit(root.left, f)

f(root.item)

self._inorderVisit(root.right, f)

#————————————————————

def __iter__(self):

“””in-order iterator for binary search tree”””

return self._inorderGen(self.root)

#————————————————————

def _inorderGen(self, root):

if root is not None:

# yield all the items in the left subtree

for item in self._inorderGen(root.left):

yield item

yield root.item

# yield all the items from the right subtree

for item in self._inorderGen(root.right):

yield item

#————————————————————