Binary search tree with equal keys. $(40$ points$)$ In the class, we assumed that all the

keys in a BST are different from each other. However, the BST can still store keys of the

same value, in this case, we put a key that is less than a node to its left, and put a key

that is greater than or equal to a node to its right. Here is the algorithm for inserting

a new key $z$ in to a binary search tree $T$ :

Algorithm $1$: Tree$-$Insert $(T,z)$

$y=$ NIL;

$x=$ T$.$root;

while $x$ NIL

$y=x$;

if $x=xx=x=yy==$NIL$=z$;$\frac{,}{\frac{?}{?}}T=zz.$key.key

$x=x.$left;

else $x=x.$right

$z.$parent $=y$;

$ify==$NIL

$T.$root $=z$;$\frac{,}{\frac{?}{?}}$ tree $T$ was empty

elseif $z.$key$=z$;

else y$.$right $=z$;

$($a$)(10$ points$)$ To better understand the algorithm, draw the tree generated by inserting

the numbers $5,3,10,8,12,12,8,8,6,6,7,5,8$ in this given order into an initially

empty binary search tree using the above algorithm.

$($b$)(10$ points$)$ What is the asymptotic runtime of TREE$-$INSERT when used to insert $n$

items with identical keys into an initially empty binary search tree?

We propose to improve TREE$-$INSERT by testing before line $5$ to determine whether

z$.$key $==x.$key and by testing before line $11$ to determine whether z$.$key$==$y$.$key. If

equality holds, we implement one of the following strategies. For each strategy, find

the asymptotic runtime of inserting $n$ items with identical keys into an initially empty

binary search tree. $($The strategies are described for line $5,$ in which we compare the

keys of $z$ and $x,$ and substitute $y$ for $x$ to arrive at the strategies for line $11.)$

$($c$)(10$ points$)$ Keep a list of nodes with equal keys at $x,$ and insert $z$ into the list.

$($d$)(10$ bonus$)$ Randomly set $x$ to either x$.$left or x$.$right. $($Give the worst$-$case runtime

and informally derive the expected runtime.$)$

$[$Note: for $($b$)($c$)$ and $($d$),$ we are expecting the runtime represented as a

function of $n.$