My preferred definition of a non-empty, full binary tree is:
Definition 0. A pointed magma is an ordered triple $(X,\bullet,\star)$, such that:
- $X$ is a set
- $\bullet$ is an element of $X,$ and
- $\star$ is a function $X \times X \rightarrow X$.
Definition 1. Write $\mathbb{T}$ for the initial pointed magma, the elements of which are called non-empty full binary trees.
For example, here's an example of a non-empty full binary tree:
$$(\bullet \star \bullet) \star \bullet \in \mathbb{T}$$
This can be visualized as a tree, of course:
Okay. Let $\varphi : \mathbb{T} \rightarrow \mathbb{N}$ denote the node-counting function. Explicitly:
Definition 2. Define a function $\oplus : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ as follows: $$a\oplus b = a+b+1$$
Definition 3. Let $\varphi : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,\oplus)$ denote the unique such homomorphism of pointed magmas. We call $\varphi$ the node counting function.
For example, $$\varphi((\bullet \star \bullet) \star \bullet) = (1\oplus 1) \oplus 1 = 3 \oplus 1 = 5$$
So the above tree has $5$ nodes, as desired.
I claim that:
Claim. For all $x \in \mathbb{T}$, the natural number $\varphi(x)$ is odd.
This prove this, we need a way of performing induction on non-empty full binary trees. Here's a theorem that lets us do this:
Structural Induction for $\mathbb{T}$.
The pointed magma $(\mathbb{T},\bullet,\star)$ has no proper subalgebras.
More explicitly:
Structural Induction for $\mathbb{T}$. (Long form.)
Let $X$ denote a subset of $\mathbb{T}$.
If
- $\bullet \in X$, and
- for all $x,y \in X$, we have $x \star y \in X$,
then
$X = \mathbb{T}$.
Now we can prove our claim. Let $X$ denote the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd.
We know that $\bullet \in X$, since $\varphi(\bullet) = 1$ and $1$ is odd.
Assume $x,y \in X$. We will show that $x \star y \in X$. We know that $\varphi(x \star y) = \varphi(x) \oplus \varphi(y) = \varphi(x)+\varphi(y)+1.$ But the sum of three odd numbers is itself odd. So $\varphi(x \star y)$ is odd.
Hence by the structural induction theorem, we have $X=\mathbb{T}$. But recall that we defined $X$ as the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. Thus $\mathbb{T}$ itself is the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. In other words, $\varphi(x)$ is always odd, for all $x \in \mathbb{T}$. QED
A further comment.
It is worth noting that we can define the leaf-counting function in much the same way:
Definition 4. Let $\lambda : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,+)$ denote the unique such homomorphism of pointed magmas.
We call $\lambda$ the node counting function.
For instance, $$\lambda((\bullet \star \bullet) \star \bullet) = (1+1)+1 = 3,$$ so the aforementioned tree has $3$ leaves, as desired.
The cool thing about $\lambda$ is that it gives what is perhaps the most fundamental definition of the Catalan numbers; namely, writing $C_n$ for the $n$th Catalan number, we can define: $$C_n = |\lambda^{-1}(n+1)|$$
For example, $$C_2 = |\lambda^{-1}(3)| = |\{(\bullet \star \bullet) \star \bullet, \bullet \star (\bullet \star \bullet)\}| = 2$$
First a side remark. As you noted, $n=c_0+c_1+c_2$. Also, we note that every node except the root is the child of exactly one other node, therefore $n-1=c_1+2c_2$. Using these two relations, we can write
$$\begin{align} c_1&=n+1-2c_0 \\c_2 &= c_0-1 \end{align}$$
And then only use $n$ and $c_0$ as parameters.
Second, the actual question. For the worst case (large $h$), you can simply put all one- and two-sibling in a single long chain, which means $h=c_1+c_2+1$. For the best case (small $h$) you make a balanced tree out of the two-children nodes. This will have height about $log_2(c_2)$ with about $c_2/2$ nodes on the lowest level. The remaining one-child nodes should be distributed into $c_2/2$ chains of equal lengths and put underneath the balanced tree. The result is something like $h\approx \log_2(c_2)+2\frac{c_1}{c_2}+1$.
So the answer you are looking for is approximately $h\in [\log_2(c_2)+2\frac{c_1}{c_2}+1,c_1+c_2+1]$. The second expression needs some appropriate rounding in case $c_2$ is not a nice number and such, but you can figure that out for yourself if neccesary.
Third, you see that the upper bound is not really good. In particular it is worse then any real actual red-black/avl tree. Maybe instead of considering strict bounds on $h$, you should think about the average $h$ over all trees with given $c_0,c_1,c_2$. That will be much closer to practical datastructures.
Best Answer
If you take $n > 0$, and remove the last binary digit to create the number $m$, then $m < n$, so in particular if $n$ is in your trie so is $m$. Thus your tree has $10^{100}$ nodes. In fact, if you write down the infinite binary tree, with the root on top, then you'll see that the numbers just appear in order, left to right, top to bottom. First, a row with 1; then a row with $2, 3$; then a row with $4, 5, 6, 7$; and so on.
From this you can also see that the first $k$ rows take up the first $2^{k} - 1$ numbers. This means that the number of layers in your tree is $$ \min \{k \mid 10^{100} \leq 2^k - 1\}. $$ That $-1$ is annoying: if it weren't there, we could simply say, well, we are looking for the least $k$ such that $100 \log(10) \leq k \log(2)$, i.e., we are looking for $$ k = \left\lceil 100 \frac{\log(100)}{\log(2)}\right\rceil. $$ But it might be that $10^{100} + 1 = 2^k$ for some $k$, in which case our $k$ is an overestimate. But fortunately, we see that this is not possible, because $2^k$ is even, and $10^{100} + 1$ is odd, so indeed our estimate of the depth is correct.