Представьте себе идеальное дерево высотой h . Когда итератор находится на первом узле (крайнем левом листе), ему нужно будет каким-то образом запомнить, с помощью каких внутренних узлов он прибыл в этот узел, потому что на одном из следующих шагов ему нужно будет получить значения в этих узлах (и их правые поддеревья). Поскольку указатели на родительские узлы отсутствуют, эта информация недоступна и должна где-то храниться.
Независимо от того, как этот путь запоминается (список внутренних узлов или список направлений, например, левый-левый-левый-левый, возможно, компактно сохраненный в битовом представлении), теоретический размер этого хранилища есть O (h).
Как отмечено в комментариях ниже, для сохранения только направлений потребуется снова пройти по пути от root на каждом этапе итерации. В качестве альтернативы вы можете запомнить последнее посещенное значение и использовать двоичный поиск, чтобы найти следующий узел. Если все значения в дереве уникальны, тогда размер памяти фактических значений будет иметь, по крайней мере, тот же порядок величины, что и компактное представление пути (побитовое лево-лево-лево ...), так что в любом случае (сохранение пути , или последнее посещенное значение) требования к хранилищу аналогичны.
Теперь, когда вы устанавливаете какой-то предел на размер дерева, конечно, нет больше смысла говорить о пространстве (или времени) сложность. Например, если дерево никогда не будет иметь высоту более 64, то текущий путь может быть представлен в виде 64-битного целого числа без знака, возможно, с некоторым дополнительным небольшим целым числом для обозначения текущего размера этого пути.
Поскольку количество атомов в наблюдаемой Вселенной оценивается в 2 250 , вы можете работать и с этим, и вместо этого использовать 256-битное целое число без знака (два длинных). Компьютерная память никогда не сможет сохранить идеальное дерево такой высоты.