Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Unidad 3/Cantidad de nodos en un árbol

Sea un árbol n-ario completo de altura h.

En el nivel 0 tendrá un solo nodo: la raíz. En el segundo tendrá nodos, en el tercero ; en general, en el nivel h tendrá nodos.

Para saber la cantidad total C de nodos que tiene el árbol completo de altura h, tendremos que sumar la cantidad de nodos de cada uno de los niveles:

Simplificando la expresión editar

 

Multiplicando ambos lados por n:

 

Restando miembro a miembro: