Suppose we use the following idea to color an AVL tree as a red$-$black tree:

$$Color non$-$root nodes red if their height is even and their parent's height is odd, and

black otherwise.$$

a$.(2$ points$)$ Prove that a red node cannot have a red child in the above scheme.

b$.(2$ points$)$ Describe the coloring of a perfect tree.

c$.(2$ points$)$ Describe the coloring of a complete tree.

d$.(10$ points$)$ Prove by induction on the tree structure that

i$.$ red nodes at a height of $2$k have k black nodes on every path to a null

pointer

ii$.$ black nodes at a height of $2$k have k$+1$ black nodes on every path to a

null pointer

iii. black nodes at a height of $2$k$+1$ have k$+1$ black nodes on every path to a

null pointer