Здравствуйте! Задумался над одной задачей — можно ли вывести все вершины произвольного дерева, использовав O(1) памяти? Почти сразу придумал обход в глубину, но при этом каждая вершина выводится не один раз. Непонятно, как избавиться от этого недоразумения. Может, есть известный алгоритм?

P.S. Спасибо всем, написали много интересных алгоритмов. Но всё-таки конкретизирую задачу: в функцию обхода передается корень дерева, в каждой вершине хранится список потомков, предок неизвестен. Возможна вторая постановка — в каждой вершине хранится массив потомков конкретной(и одинаковой для всех вершин) длины. Автору известно решение первой задачи, при которой в каждую вершину заходится 1+количество потомков вершины раз. Также, автору известно решение второй задачи для бинарного дерева(обход Морриса). Больше автор ничего придумать/нагуглить не смог.