there is is an alternative solution where you basically do it using an inorder traversal. it uses more stack space because it holds 1 node pointer in global state and two node pointers between the left and right recursion. While the building a list solution just holds a single node pointer during the left and right recursion.<p>lets say you want to convert a tree to single linked list in order then you can just do an in order traversal of the tree and keep track of the previous node and assign previous.left = current_node and this is fine because if you are at the successor to a node then the whole of the previous nodes left subtree has been visited because it is smaller and you will never need to follow the left pointer again.<p><pre><code> previous = nil
in_order(tree) do |node|
if previous
previous.left = node
end
previous = node
end
</code></pre>
however, you can't do node.right = previous until you have visited the right subtree of the current node so you can't use exactly the same code for a doubly linked list. however, if you do the fix up after you have finished processing the current node then it works fine. so if you have an iteration that will give you both an inorder and postorder callback and a way of sharing state between them you can just do the fixup in the postorder callback where it is safe.<p><pre><code> previous = nil
head = nil
multi_order(tree) do |node, order, state|
if order == :inorder
if previous
fixup_state = [node, previous]
else
head = node
end
previous = node
fixup_state #passed back into iterator and is return in post_order callback
else
if state
fixup_node, fixup_previous = state
fixup_previous.left = fixup_node
fixup_node.right = fixup_previous
end
end
end
previous.next = head
head.prev = previous
head</code></pre>