Numero massimo di nodi per livello

• In un albero binario il numero massimo dei nodi di livello i è pari a 2i-1 con i>=1:

  • Si dimostra per induzione su i. Infatti per la radice è immediato. Dato che ogni nodo può avere al massimo due figli per il livello i il numero massimo dei nodi è pari a 2 volte il numero massimo di nodi del livello i-1