ME5751 Homework 3
We have an unsorted list: [1, 38, 2221, 63, 975, 4563, 242, 373, 93]
a. Write down its binary search tree by inserting elements in the above order, the root
should be the first element. (Hand written your result, show at least first few steps)
b. Identify whether the following numbers are on the tree or not: 3452, 373. Show your
search steps. (Hand written your result, then write python program to valid it)
c. (bonus) Can you write your search function in both recursive and non-recursive way?

class node:
def __init__(self, value = 10):
self.parent = None
self.left = None
self.right = None
self.value = value

# A utility function to insert a new node with the given key
def insert(root,node):
if root is None:
root = node
else:
if root.value < node.value:
if root.right is None:
root.right = node
node.parent = root
else:
insert(root.right, node)
else:
if root.left is None:
root.left = node
node.parent = root
else:
insert(root.left, node)