# Least-balanced possible red-black tree of n distinct nodes

Let's say we have a red-black tree of $$n$$ total nodes where all keys are distinct. The subtree rooted at the root node's left child has $$n_L$$ nodes, and similarly the subtree rooted at the root node's right child has $$n_R$$ nodes.

What is the range of values on $$n_L$$ and $$n_R$$ for any $$n \geq 3$$? For example, in the above image: $$n = 8, n_L = 1, n_R = 6$$.

Let $$b$$ be the black height of the left subtree, which is also the black height of the right subtree.

The number of nodes in the left subtree is at least $$2^{b}-1$$. $$2^b-1$$ is reached when the left subtree is a perfect binary tree of black nodes and height $$b-1$$.

The number of nodes in the right subtree is at most $$2^{2b+1}-1$$. $$2^{2b+1}-1$$ is reached when the root is black and the right subtree is a perfect binary tree of height $$2b$$ with nodes colored red, black, red, black and so on alternatively from top to bottom.

$$2^b-1 + 2^{2b+1}-1\ge n-1$$

Solving for $$b$$, we obtain $$b\ge f(n) := \lceil \log_2(\sqrt{8n+9}-1)\rceil-2$$

So, the range for $$n_L$$ is $$[2^{f(n)}-1, n - 2^{f(n)}]$$, which is, by symmetry, also the range for $$n_R$$.

For example, when $$n=8$$, $$f(n)=1$$, the range is $$[1, 6]$$ as illustrated in the question.