Nächstes Element in einem binären sortierten Baum

Gegeben sei ein Wert k V, gesucht wird der
Knoten n(T, k) = u T mit
v(u) > k und ¬ exists u' T: v(u') > k und v(u') < v(u).

1. Wenn T leer ist, dann gibt es kein solches Element.

2. Sei t = root(T).

3. Falls k v(t), dann ist n(T₂, k) das gewünschte Element (falls existent).

4. Falls hingegen k < v(t), dann ist es n(T₁, k), falls existent, oder andernfalls t.

Das erste Element eines binären sortierten Baumes läßt sich leicht bestimmen, indem ganz nach links abgestiegen wird.