Modify binary search trees so that to support the following operations:

$1.$ TREE$-$SEARCH$($T$,$k$)-$ return the element in T that has key k; if no element in T has

key k$,$ return NIL.

$2.$ INSERT$($T$,$ x$)-$ insert an element x into T $($assume T contains no objects with key

x$.$key$)$

$3.$ DELETE$($T$,$x$)-$ delete an element x from T $($assume x is in T$)$

$4.$ COUNT$($T$,$x$)-$ here x is a node in T; return the number of descendants of x that have

two children.

Procedures TREE$-$SEARCH, INSERT and DELETE may have to be modified from their

original binary search tree counterparts. Explain why or why not modifications are needed

$(0\mathrm{.}5$ pt$).$ Describe the modifications $($no need for a pseudo$-$code$)$ just a narrative how the

procedures would change $(1$ pt$).$ Estimate the running time of your solution $(0\mathrm{.}5$ pt$).$ For

full credit correct optimal solutions are required.