Двоичное дерево поиска можно обойти без стека и рекурсии: https://en.wikipedia.org/wiki/Threaded_binary_tree
Цоперайт © 2010-2016 @stiletto.
Двоичное дерево поиска можно обойти без стека и рекурсии: https://en.wikipedia.org/wiki/Threaded_binary_tree
Вот здесь нормальный код: https://prismoskills.appspot.com/lessons/Binary_Trees/Traversal_without_recursion_or_stacks.jsp
@l29ah Лень искать оригинальный папир, но на глазок это дело выглядит константным по памяти и логарифмическим по времени.
а нужно ли?
@goren Во-первых, науке безразлично, нужно или нет: её интересует только «можно ли». Во-вторых, несложно представить ситуацию, когда у тебя мало памяти, а на вход могут быть поданы деревья произвольного размера, которые нужно обходить.