Как обойти дерево без вложенной функции

Условие

Нужно вернуть значения дерева в прямом обходе: узел, затем дети слева направо. У узла поля value и children. Можно ли обойтись без вложенной рекурсивной функции?

Ответ

Да: используйте явный стек. Добавляйте детей в обратном порядке, чтобы при извлечении они посещались слева направо.

Пример Python:

def preorder(root):
    if root is None:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.value)
        stack.extend(reversed(node.children))
    return result

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