$[4$ marks$]$ Define right$-$leaning red$-$black BSTs as BSTs having red and black edges satisfying the following

three restrictions:

i$.$ Red links lean right only.

ii$.$ No node has two red links connected to it$.$

iii. Every path from the root to a leaf has the same black depth.

Rewrite the put$()$ method, given in the Sedgewick book $($also on the second last slide of Lecture $18),$

so that it works for right$-$leaning red$-$black trees instead of left$-$leaning red$-$black trees