Perfect Binary Tree

A perfect binary tree is a binary tree in which all interior (non-leaf) 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 perfect binary tree with depth $d$ is:

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

For example, the perfect binary tree of depth $2$ above has $2^3 – 1 = 7$ nodes. Now, consider the formula above for the number of nodes in a perfect 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 $\lg(n+1) - 1$, which is in $\Omicron(\lg n)$.