Implement the following function: def restore_bst(prefix_lst) The function is gi
ID: 3713574 • Letter: I
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 funct(ion.
(PYTHON)
Explanation / Answer
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