relation according to height factor between two specific trees

Question

I have $2$ trees as follows:

$First$

$Second$

I want to find a relation between these two trees, I need this relation: if we get height of the second three as $H$ what is the relation between $height$ of these two example according to $H$?

Answer 1

The height of the second tree is $n$, the length of the path from the vertex $2^0$ to the root. Problem $5$ in the PDF specifies that $n+1=2^N$, so $\log_2(n+1)=N$, and the claim is that the height of the first tree is $N$. To see this, let $h$ be the height of this tree; it has $2^N$ leaves, and they are on level $h$. Clearly level $h-1$ has half as many nodes as level $h$, so it has $2^{N-1}$ nodes. Similarly, level $h-2$ has $2^{N-2}$ nodes, and in general level $h-i$ has $2^{N-i}$ nodes for $i=0,\ldots,N$. Thus, level $h-N$ has $2^{N-N}=1$ node; clearly that node is the root of the tree, so it is on level $0$, i.e., $h-N=0$. But then $h=N$, as claimed.