If a key in a red-black tree has exactly one child (which isn't null) then he is always red

Question

I have the following claim:

If a key in a red-black tree has exactly one child (which isn't null) then he is always red. prove or disprove it.

---

My attempt:

$Disproof.$

we shall represent a counter-example:

This tree satisfies the conditions of being a red-black tree,

since:

1. the root is black.
2. all leaves are black.
3. there isn't a red key.
4. in each path there is the same amount of black keys, in particular, we have three black keys in such paths.

However, we have two keys in level-1, which have one child and he is black.

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \blacksquare$

---

Is this disproof right? because perhaps I missed something, and this counter-example doesn't represent a counter-example. Thanks!

Answer 1

There are two equivalent descriptors of red-black trees. In one, all leaves are supposed to be (black) nulls. In another, these are suppressed. The example you give can only be interpreted as a red-black tree in this later interpretation. However, then the paths that appear in the definition are not to what appears to be leaves in the picture, but to these invisible null leaves. Then it is clear that there are paths to null leaves with different numbers of black nodes. In conclusion, the picture you provide does not describe a red-black tree.