Convert a binary tree to linked list, breadth first, constant storage/destructive
- by Merlyn Morgan-Graham
This is not homework, and I don't need to answer it, but now I have become obsessed :)
The problem is:
Design an algorithm to destructively flatten a binary tree to a linked list, breadth-first. Okay, easy enough. Just build a queue, and do what you have to.
That was the warm-up. Now, implement it with constant storage (recursion, if you can figure out an answer using it, is logarithmic storage, not constant).
I found a solution to this problem on the Internet about a year back, but now I've forgotten it, and I want to know :)
The trick, as far as I remember, involved using the tree to implement the queue, taking advantage of the destructive nature of the algorithm. When you are linking the list, you are also pushing an item into the queue.
Each time I try to solve this, I lose nodes (such as each time I link the next node/add to the queue), I require extra storage, or I can't figure out the convoluted method I need to get back to a node that has the pointer I need.
Even the link to that original article/post would be useful to me :) Google is giving me no joy.
Edit:
Jérémie pointed out that there is a fairly simple (and well known answer) if you have a parent pointer. While I now think he is correct about the original solution containing a parent pointer, I really wanted to solve the problem without it :)
The refined requirements use this definition for the node:
struct tree_node
{
int value;
tree_node* left;
tree_node* right;
};
