# Prove that the subtree rooted at any node $x$ in a red black tree contains at least $2^{bh(x)} - 1$ internal nodes

To prove this, Introduction to Algorithms by Cormen et al., makes the assumption that the node has two children.

For the inductive step, consider a node $$x$$ that has positive height and is an internal node with two children. Each child has a black-height of either $$bh(x)$$ or $$bh(x) - 1$$, depending on whether its color is red or black, respectively. Since the height of a child of $$x$$ is less than the height of $$x$$ itself, we can apply the inductive hypothesis to conclude that each child has at least $$2^{bh(x) - 1} - 1$$ internal nodes. Thus, the subtree rooted at x contains at least $$(2^{bh(x) - 1} - 1) + (2^{bh(x) - 1} - 1) + 1 = 2^{bh(x)} - 1$$ internal nodes, which proves the claim.

How does this extend to red black trees in general? The author defined red black trees using these five properties, none of which stops a black node from having only one child.

A red-black tree is a binary tree that satisfies the following red-black properties:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

• Correct, in that case the black height would be 1 through the path to NIL, and consequently in general. Thus, the number of internal nodes has to be $2^1 - 1 = 1$, which holds true. Apr 9, 2023 at 6:17