Suche nach einem Rank in einem Binärbaum

#1
Vorgegeben ist eine abstrakte Datenstruktur in Form eines Binärbaums, bei der ein Objekt einen Schlüssel x und den Größe des linken/ rechten Teilbaums speichert. Ich habe bereits eine Methode rankofElement(x) implementiert in Pseudocode, welche den Rang eines Knotens x zurückgibt:
function rankofElement(x) {
rank = 0;
Node temp = root;

while (temp.key != x) {
if (x < temp.key) {
temp = temp.leftson
} else if (x > temp.key) {
rank += temp.leftson.size + 1;
temp = temp.rightson;
} else if (temp.key == x) {
return rank + temp.leftson.size
} else return "key not found"
}


Jetzt soll ich die Methode elementbyRank(k) in Pseudocode implementieren welche einen Knoten mit dem Rang k innerhalb eines Binärbaums wiedergibt. Außerdem soll die Laufzeit maximal O(h) betragen, wobei h die Höhe des Baums ist. Ich hoffe ihr könnt mir helfen!
 
Oben