Define the print_insert_position() function which is passed two parameters: a binary search tree, and a value to be inserted into the tree. The function does not modify the tree at all, it prints the position at which value would be inserted into the tree. The function prints either "To the left of " or "To the right of " followed by the node value under which the parameter value is to be inserted.

If the data value to be inserted already exists in the tree, then the function should print "Duplicate".

You can assume the following BinarySearchTree class is available and you should not need to include this class in your answer.

class BinaryTree: def __init__(self, data): self.data = data self.left = None self.right = None def insert_left(self, new_data): if self.left == None: self.left = BinaryTree(new_data) else: t = BinaryTree(new_data) t.left = self.left self.left = t def insert_right(self, new_data): if self.right == None: self.right = BinaryTree(new_data) else: t = BinaryTree(new_data) t.right = self.right self.right = t def get_left(self): return self.left def get_right(self): return self.right def set_left(self, tree): self.left = tree def set_right(self, tree): self.right = tree def set_data(self, data): self.data = data def get_data(self): return self.data 

The header for the function is:

def print_insert_position(bs_tree, value): 

For example:

Test	Result
a = BinaryTree(100) print_insert_position(a, 29)	To the left of 100
a = BinaryTree(50) a.insert_left(10) a.insert_left(20) a.insert_left(30) a.insert_left(40) print_insert_position(a, 5)	To the left of 10