Methods for binary search trees. Let T be a binary trees that has n items stored in its internal nodes. Each node v has a field v$.$size that is equal to the number of items stored in its subtree Tv$.$ For example, when v is an external node v$.$size $=0.$ Consider the following methods:

$1.$ countAllElements$($T$,$ k$)$: returns the number of items in T whose keys equal k$.$

$2.$ rank$($T$,$ v$)$: returns the rank of v$.$key in T$,$ the number of items in T whose keys are strictly

smaller than v$.$key.

Design algorithms for both methods that run in O$($T$.$height$)$me$.$ Explain why your algorithms are correct and justiy their running $$mes