We have a sorted array A of n $=2$k$-1$ unique numbers. Assume A is indexed a $..$ b$.$ The following recursive algorithm will insert them into an empty BST and produce a full BST$.$ Assume tree is an empty BST$.$

Call: bst$\_$balanced$($A$,$ a$,$ b$,$ tree$)$

bst$\_$balanced$($A$,$ lo$,$ hi$,$ tree$)$

if $($lo $<=$ hi$)$

m $=($lo $+$ hi$)//2$

tree.insert$($A$[$m$])$

bst$\_$balanced$($A$,$ lo$,$ m$-1,$ tree$)$

bst$\_$balanced$($A$,$ m$+1,$ hi$,$ tree$)$

$($a$)$ Suppose the array A $=\{1,3,5,6,8,11,13,15,20,22,23,25,28,30,33],$ and n$=15.$ Show the BST after the first $6$ insertions

$($b$)$ Write the recurrence T$($n$)$ for the general case.

$($c$)$ If n$=1023$ and lo $=1$ and ho $=1023,$ the $1$st to be inserted is at index $512.$ Determine the index of the $513$th node to be inserted. Explain your answer.

$($d$)$ What is the maximum number of nodes we could add into the tree in $($c$)$ and only increase the tree height by $1?$ Explain your answer.