Perfect Binary Tree

A perfect binary tree is a binary tree in which all interior nodes have two children, and all leaves have the same depth or same level

You can verify this by looking at the example above: a perfect binary tree has $1$ node at level (depth) $0$, $2$ nodes at level $1$, $4$ nodes at level $2$, and so on. Thus, it will have $2^d$ nodes at level $d$. Adding these quantities, the total number of nodes $n$ for a full binary tree with depth $d$ is:

$$n = 2^0 + 2^1 + 2^2 + \dots + 2^d = 2^{d+1} − 1$$

For example, the full binary tree of depth $2$ above has $2^3 – 1 = 7$ nodes.

Now, considering the formula above for the number of nodes in a full binary search tree:

$$n = 2^{d+1} − 1$$

Solving for $d$, we get:

$$n+1 = 2^{d+1}$$

$$\lg(n+1) = \lg(2^{d+1})$$

$$\lg(n+1) = (d+1)\lg(2)$$

$$\lg(n+1) = (d+1)$$

$$d = \lg(n+1) - 1$$

We know the height of the tree is the depth of the deepest node. So the height of a perfect binary tree is at most $\lg(n+1) - 1$ or $\Omicron(\lg n)$.