# Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes

I have a red-black tree with $$n$$ nodes, rooted at $$x$$. How can I prove or disprove that the number of nodes in any subtree of $$x$$ (including the root of the subtree) will never be greater than $$\frac{3n}{4}$$?

Here is a natural approach to explore the extreme case.

Let node $$r$$ be the root of a red-black tree.

Let its left subtree be a red-black tree of black height $$h$$ that has the minimum number of the nodes among red-black tree of the same black height.

Let its right subtree be a red-black tree of the same black height $$h$$ that has the maximum number of the nodes among red-black tree of the same black height.

Now let $$h=1,2,3,\cdots$$ be larger and larger. Can you see the trend?

Here is a related exercise.

Exercise (red-black trees may not be weight-balanced). Given $$\alpha\lt 1$$, show that there is a red-black tree which has a proper subtree that has more than $$\alpha$$ of all nodes.