Height is $O(\lg N)$

In a BBST, unlike a regular BST, it is guaranteed that the tree's height is $O(\lg N)$. This claim can be easily observed for a perfect BST, where each internal node has two children and all the leaves are at the same level.

Let's observe the full BSTs above

Given these full BSTs, one can intuit how this holds more generally.

First, convince yourself that the worst height of a BST is when it has the minimum number of nodes concerning its height. Then, let's call $N(h)$ the minimum number of nodes given height.

The worst case $h \in O(n)$ is when $N(h) = h+1$.

If we find the upper bound of $N(h)$ for BBST, then we've bounded the height of all BBSTs.

Let's consider a BBST of height $h \geq 3$ and the minimum number of nodes $n=N(h)$. This tree is composed of a root and two subtrees. Since the whole tree has the minimum number of nodes for its height, so do the subtrees. For the big tree to be of height $h$, one of the subtrees must be of height $h-1$. To get the minimum number of nodes, the other subtree is of height $h-2$.

So far, we established for $h \geq 3$,

$$ N(h) = 1 + N(h-1) + N(h-2) $$

We know

$$ N(h) > N (h-1)​ \space \text{and} \space N(h-1) > N(h-2)​ $$

therefore

$$ N(h) > N(h-1) + N(h-2) > 2\times N(h-2) $$

If $N(h) > 2\times N(h-2)$ then $N(h-2) > 2\times N(h-4)$, therefore

$$ N(h) > 2\times N(h-2) > 4 \times N(h-4) $$

We can keep doing this

$$ N(h) > \dots > 4\times N(h-4) > 8\times N(h-8) > \dots $$

Continuing the proof, we see that this can be written as:

$$ N(h) > 2^i \times N(h - 2i) $$

The largest $i$ we can put in there is $i = \frac{h}{2} - 1$:

So we have:

$$ N(h) > 2^i \times (h-2i) > 2^{\frac{h}{2}} \times N(h - h) > 2^{\frac{h}{2}} $$

What does this say about height, $h$? First, let's take the logarithm of both sides:

$$ \lg n > \lg 2^{\frac{h}{2}} \Rightarrow h < 2\lg(n) $$

So, $h \in O(\lg n)$.