Существует префиксное дерево (нагруженное дерево, trie).
Дерево хранит в себе пару ключ/значение. Необходимо реализовать упорядоченный обход дерева по значению, т.е. необходимо идти от ветвей с наибольшим значением к ветвям с наименьшим. Поскольку первая и вторая пары результирующего набора могут быть в противоположных ветвях, то возникают сложности.
Обновление
Дерево никак не отсортировано. У каждого узла может быть бесконечно потомков. Думаю хранить в каждом узле максимальное значение на этой ветви. И пытаться делать прицельный обход.