O-Notation - Aufwand für Einfügen im binären Suchbaum

Question

Geben Sie den minimalen, den mittleren und den maximalen Aufwand für das 
Einfügen in einem binären Suchbaum in O-Notation an. 

Kann mir da einer helfen? + Begründung wäre TOP fürs Verständnis:)

Answer 1

Minimaler Aufwand ist O(1): Der Baum ist zu einer Liste entartet und es wir ein zweites Kind zur Wurzel hinzugefügt.

Maximaler Aufwand ist O(n): Der Baum ist zu einer Liste entartet und es wir ein Kind zum Blatt hinzugefügt.

Mittler Aufwand ist O(log₂ n): Der Baum relativ ausbalanciert. Dann hat er bei n Knoten die Tiefe von O(log₂ n).