Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 1 / c / Solution

No. In a red-black tree with no red nodes, equal black height forces every graph path from the root to an absent-child position to have the same length. A real node cannot have exactly one real child: the two paths through that node would then have different numbers of black nodes. Recursively, every real level must be full. The tree is therefore a perfect binary tree.

With $h$ real levels its size is $1+2+\cdots +2^{h-1}=2^h-1$. A size of $23$ would require $2^h=24$, which is impossible for an integer $h$. The black null sentinels are not counted among the $23$ stored entries. This is the all-black red-black tree size criterion.