$($a$)(16$ points$)$ Given a binary search tree of height h$,$ show how to implement range$($x$,$ y$)$ in O$($h$+$k$)$

time, where k is the number of elements that are at least x and at most y$.$

Can we do this operation even faster? It turns out that we can! In particular, for a binary search

tree of height h$,$ we can do this in O$($h$)$ time. We will prove this in the rest of the problem.

$($b$)(17$ points$)$ Describe an extra piece of information that you will store at each node of the tree,

and describe how to use this extra information to do the above range query in O$($h$)$ time.

Hint: Think of keeping track of a size.

$($c$)(17$ points$)$ Describe how to maintain this information in O$($h$)$ time when a new node is inserted

$($note that there are no rotations on an insert $$ it$$s just the regular binary search tree insert, but

you need to update information appropriately$).$