Beim Einfügen eines Knotens in einen Binärbaum ist darauf zu achten, dass die Ordnung der im Baum gespeicherten Werte erhalten bleibt.
Das Einfügen erfolgt mit einem rekursiven Algorithmus wie folgt:
- Nimm den Wurzelknoten als aktuellen Knoten.
- Ist der einzufügende Wert kleiner/größer als der Wert des aktuellen Knotens, gehe weiter in den linken/rechten Unterbaum. Wenn der Unterbaum leer ist, dann füge den neuen Knoten hier ein.
Wenn der Knoten nicht eingefügt wurde (weil der Unterbaum nicht leer ist), dann nimm den Wurzelknoten des rechten/linken Unterbaums als aktuellen Knoten. Weiter mit 2 (Rekursion).