Weighted binary search tree
Show by induction on the height $h$ of the tree that a tree of height $h$ has at least $2^{\frac{h}{2}}$ nodes.
The base case $h=0$ is easy since a tree of height $0$ has $1$ vertex and $1 \ge 2^\frac{0}{2}$.
Suppose that the claim holds up to some $h \ge 0$. Consider a tree $T$ with height $h+1$ rooted in $r$. Let $u$ and $v$ be the children of $r$. Let $n(x)$ and $h(x)$ denote the number of nodes and the height of the subtree of $T$ rooted at $x$, respectvely.
We must have $h(r) = 1 +\max\{h(u), h(v)\}$. Suppose w.l.o.g. that $h(r)=1+h(u)$. Then, regardless of whether $u$ is the left or right child of $r$, we have $\frac{n(v)}{n(u)} \ge \frac{1}{2}$, i.e., $n(v) \ge \frac{n(u)}{2}$.
$$
\begin{align*}
n(r) &amp;= 1 + n(u) + n(v) &gt; n(u) + \frac{n(u)}{2} = \frac{3}{2} \cdot n(u) \\
&amp;\ge \frac{3}{2} \cdot 2^{\frac{h(u)}{2}} 
= \frac{3}{2} \cdot 2^{\frac{h(r)-1}{2}}
= \frac{3}{2} \cdot 2^{\frac{h}{2}} 
&gt; 2^{\frac{1}{2}} \cdot 2^{\frac{h}{2}} =  2^{\frac{h+1}{2}}.
\end{align*}
$$
This concludes the proofs, and shows that a tree with $n$ nodes has height at most $2 \log n$.