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

Question

I have the following claim:

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

---

My attempt:

Disproof.

We will exhibit a counterexample:

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 any 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 it is black.

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

---

Is this counterexample correct?

Answer 1

The disproof is wrong because in your Red-Black tree, all possible leaves need to be represented (see exemples on wikipedia). That means that the real tree represented should be:

It is easy to see that it does not respect the fourth condition of the definition.

In the claim, when it is said that:

a key […] has exactly one child (which isn't null)

it actually means that it has two children, and exactly one of them is null. It is due to the fact that in the representation of a red-black tree, you can either represent ALL null leaves or represent none.

I will let you try to prove or disprove the claim knowing that and edit this answer if necessary.