Bevor ich die neue Version von meinem Alg. bringe, vorab die folgenden Bemerkungen, die Dir vllt von Hilfe sein können. Für die Traversierung, die der von Dir vorgeschlagenen Ameise ("Ameisenweg") folgt, sind im Knoten für den Abstieg zu den Blättern die 2 Kind-Zeiger erforderlich (und wohl auch immer vorhanden). Für den Wiederaufstieg (in der Gegenrichtung der Kante (edge)) ist der Zeiger zum Elter und die Chiralität (ob ein Knoten linkes oder rechtes Kind ist) erforderlich. Die beiden können aus irgendwelchen Gründen schon vorhanden sein. Man kann sie sich aber auch beim Abstieg in einem Stapelspeicher (Stack) merken. Hat man den Elterzeiger (egal, ob im Knoten oder im Stack), dann hat man auch die Chiralität (durch den bekannten Vergleich der Zeiger beim Aufstieg). Hat man ihn nicht und will man sich auch keinen Stack dafür leisten, dann kann man sich den Elterzeiger im Abstieg an der Stelle desjenigen Kindzeigers, zu dem man absteigt, merken. Allerdings verliert man dann die Chiralität, weil der bekannte Vergleichs nicht mehr geht. Für die Chiralität gibt es dann m.E. die folgenden 3 Möglichkeiten (die Restauration des Kindzeigers gelingt beim Wiederaufstieg mithilfe der Chiralität!): Stack (1 Bit pro Level), also zus. space = O(h), zus time = O(n) [time war vorher schon O(n)]. Das ist m.E. äquivalent zu Deinem cnt, der ja auch sowohl im Knoten wie in einem Stack gehalten werden kann. Adress-"Inversion" (link reversal?) von Hirschberg.Seiden.1993 mit zus. space = O(1); aber zus time = O(n) [war vorher schon O(n)]. Nochmal Vergleichen des key (von Kind und Elter) mit zus. space = O(1); zus time = O(n) [war vorher schon O(n)]. Das erfordert aber, dass der Baum ein Suchbaum ist und dass es keine Duplikate in ihm gibt. Alle diese 3 Möglichkeiten sind in der Zeitkomplexität gleich. Der Rest des Algorithmus, der "Ameisenweg" ist im Prinzip davon unberührt. Viele Grüße - Nomen4Omen 12:09, 14. Mär. 2020 (CET)