mplement 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:

$39$

$13$

$373$

$3$

$11$

$15$

$333$

$3135$

Notes:

$1.2.3.4.$ The runtime of this function should be linear.

Assume that prefix$\_$lst contains integers.

Assume that there are no duplicate values in prefix$\_$lst$.$

You may want to define a helper function.