2. Define right-leaning red-black BSTs as BSTs having red and black edges satisfying the following three restrictions: i. ii. iii. Red links lean right only. No node has two red links connected Every path from the root to a leaf has the same black depth. to it. (a) Rewrite the put0 method, on page 439 of the Sedgewick book, so that it works for right-leaning red-black trees instead of left-leaning red-black trees. b) Using a construction proof, show that for every right-leaning red-black tree there is a corresponding left-leaning red-black tree. 2. Define right-leaning red-black BSTs as BSTs having red and black edges satisfying the following three restrictions: i. ii. iii. Red links lean right only. No node has two red links connected Every path from the root to a leaf has the same black depth. to it. (a) Rewrite the put0 method, on page 439 of the Sedgewick book, so that it works for right-leaning red-black trees instead of left-leaning red-black trees. b) Using a construction proof, show that for every right-leaning red-black tree there is a corresponding left-leaning red-black tree