Essendo l' albero "ordinato" alfabeticamente, non credo che tu possa avere un altro metodo per vedere la distanza di levensthein di ogni singolo figlio.
Potresti avere anche un altro albero r&b ordinato - passami il termine -con altri criteri, come la grandezza della stringa (la distanza sarà minore sicuramente con due stringhe di pari lunghezza) ; ma non credo che sia una soluzione computazionalmente migliore.