Hallo,

die maximale Anzahl der Knoten solltest du alleine ermitteln können, das ist wirklich nicht schwer. Im Zweifelsfall: Mal dir den Baum ainfach mal auf.

Bei der minimalen Anzahl kommt es darauf an, ob der Baum ausgeglichen ist oder nicht.

Ein entarteter, nicht ausgeglichener Baum hätte gerade mal \(h\) Knoten (pro Knoten nur einen Abkömmling).

Schauen wir uns den minimalen ausgeglichenen Baum an, und zwar rekursiv von der Wurzel her: Die Wurzel besitzt zwei Abkömmlinge, die ebenfalls ausgeglichene Bäume sind. Und „ausgeglichen“ bedeutet, dass die Höhe der Abkömmlinge sich um maximal \(1\) unterscheiden darf. Das liefert uns die Rekursionsformel

\[ F(h) = 1 + F(h-1) + F(h-2) \]

(Die erste \(1\) steht für den Wurzelknoten selbst.) Klingelt da etwas? So eine ähnliche Formel schon mal gesehen? Ganz berühmt! F...

Für den Abschluss der Rekursion brauchen wir noch

\[ F(1) = 1 \,, \qquad F(0) = 0 \]

Ich glaube nicht, dass es dafür eine geschlossene Formel gibt.