Здравствуйте, все.

А вот такая постановка задачи:

Дано двусвязное бинарное дерево (т.е. дочерние узлы знают о родительских).

Пусть мы хотим выполнить обход в ширину, не заводя никаких дополнительных структур.
Вопрос: можно ли, и если да, то как, воспользоваться самими узлами дерева.

Естественно, на время работы мы изменяем дерево, превращая его либо в другое дерево, либо вообще не в древовидную структуру.
Можно ли сделать это обратимым способом, чтобы по окончании мы вернули дерево в исходное состояние?

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