Question

Implement the following function: def restore_bst(prefix_lst) The function is given a list prefix_lst, which contains keys, given in an order that resulted from a prefix traversal of a binary search tree. When called, it creates and returns the binary search tree that when scanned in prefix order, it would give prefix_lst. For example, the call restore_bst([9, 7, 3, 1, 5, 13, 11, 15]), should create and return the following tree: Notes: 1. The runtime of this function should be linear. 2. Assume that prefix_lst contains integers. 3. Assume that there are no duplicate values in prefix_lst. 4. You may want to define a helper function.

Answer 1

see explaination

Step-by-step explanation:

Call to restore_bst():

prelist = [10, 5, 1, 7, 40, 50]

root = restore_bst(prelist)

Functiion implementation:

def restore_bst(prelist):

restore_bstUtil.preIndex = 0

size = len(prelist)

return restore_bstUtil(prelist, prelist[0], INT_MIN, INT_MAX, size)

def restore_bstUtil(prelist, key, min, max, size):

if (restore_bstUtil.preIndex >= size):

return None

root = None

if (key > min and key < max):

root = Node(key)

restore_bstUtil.preIndex = restore_bstUtil.preIndex + 1

if (restore_bstUtil.preIndex < size):

root.left = restore_bstUtil(prelist,

prelist[restore_bstUtil.preIndex], min, key, size)

root.right = restore_bstUtil(prelist,

prelist[restore_bstUtil.preIndex], key, max, size)

return root