Uma árvore completa é uma árvore binária na qual todas as folhas estão no mesmo nível k. Sendo k a profundidade da árvore (tamanho). Para se calcular o número total de nós utiliza a seguinte fórmula (2^k+1– 1) e para calcular número total de folhas utiliza a seguinte fórmula (k2).

Embora uma árvore binária completa possua muitos nós (o máximo para cada profundidade), a distância da raiz a uma folha qualquer é relativamente pequena.

A árvore da figura abaixo tem profundidade 3, então utilizando a fórmula para calcular a quantidade de nós:

(2^k+1– 1)
(2³⁺¹– 1)
(2^{4 - 1})
(16 – 1) = 15, então temos 15 nós.