Реализация итератора над двоичным деревом поиска

Недавно я кодировал кучу различных реализаций двоичного дерева поиска (AVL, splay , treap), и мне любопытно, есть ли особенно «хороший» способ написать итератор для обхода этих структур. Решение, которое я использовал прямо сейчас, состоит в том, чтобы каждый узел в хранилище BST указывал на следующий и предыдущий элементы в дереве, что сокращает итерацию до стандартной итерации связанного списка. Тем не менее, я' м не очень доволен этим ответом. Это увеличивает использование пространства каждого узла на два указателя (следующий и предыдущий), и в некотором смысле это просто обман.

Я знаю способ построения итератора двоичного дерева поиска, который использует пространство вспомогательной памяти O (h) ( где h - высота дерева) с использованием стека для отслеживания пограничных узлов для дальнейшего изучения, но я сопротивлялся кодированию этого из-за использования памяти. Я надеялся, что есть способ создать итератор, который использует только постоянное пространство.

У меня такой вопрос - есть ли способ разработать итератор над двоичным деревом поиска со следующими свойствами?

1. Элементы посещаются в в порядке возрастания (т.е. обход по порядку)
2. next () и hasNext () запросы выполняются за время O (1).
3. Использование памяти составляет O (1)

To сделать это проще, это нормально, если вы предположите, что древовидная структура не меняет форму во время итерации (то есть без вставок, удалений или вращений), но было бы действительно здорово, если бы существовало решение, которое действительно могло бы справиться с этим.