Нерекурсивная процедура обхода бинарного дерева за время O(n)

Я читаю книгу под названием «Введение в алгоритмы». Думаю, многие из вас это знают. Я только что столкнулся с вопросом, который кажется довольно сложным:

Напишите нерекурсивную процедуру с временем O(n), которая для заданного бинарного дерева с n узлами выводит ключ каждого узла. Используйте не более чем постоянное дополнительное пространство за пределами самого дерева и не изменяйте дерево, даже временно, во время процедуры.

Я видел, что есть еще один вопрос, подобный этому: Как обойти бинарное дерево за время O(n) без дополнительной памяти, но главное отличие в том, что я не могу модифицировать дерево. Я думал об использовании какого-то посещенного флага, но еще не нашел правильного решения. Может быть, это что-то очевидное, чего я не вижу. Как бы вы разработали алгоритм, решающий эту проблему? Даже некоторые указатели на ответ будут оценены.