Suppose that we “absorb” every node in a red-black tree into its black parent, so that the children of the red node become children of the black parent. (Ignore what happens to the keys.) What are the possible degrees of a black node after all its red children are absorbed? What can you say about the depths of the leaves of the resulting tree?

As defined in appendix B.5, the degree of a tree node is the number of children or direct descendants of the node. Leaf nodes are included in the degree.

Our absorbing black node will have a degree of \(2\), \(3\) or \(4\). \(2\) if it already had two black children, \(3\) if it had one black child and one red child and \(4\) if it had two red children (which by definition must each have two black children).

Based on red-black tree property 5, we know that after absorption our new tree’s leaves will all have the same depth.