Python 3

1. The class BST describes a node in a binary search tree. Trace the execution of the following program that builds a binary search tree. class BST (object): # Constructor def init..(self, item, left-None,right-None): self.item -item self.left left self.right right def Insert (T,nevItem): if T None: elif T.item nevItem: else: . BST(newItem) T.left Insert (T.left,novItem) T.right Insert (T.right,newItem) return T T None A [70. 50, 90, 130, 150, 40, 10, 30. oo] for a in A: T- Insert (T,a) 2. Write a function that prints all the keys in a binary search tree in ascending order given a reference to its root. 3. Write a function that receives a reference to the root of a binary search tree and returns a reference to the node that contains the smallest item in the tree. contains the largest item in the tree. to the node where k is, or None if k is not in the tree. 4. Write a function that receives a reference to the root of a binary search tree and returns a reference to the node that 5. Write a function that receives in integer k and a reference to the root of a binary search tree and returns a reference 6. Write a function that receives a reference to the root of a binary search tree and returns the number of nodes in the 7. Write a function that returns the height of a binary search tree given a reference to its root. tree