changing a tree into a list question..
i got a BST tree
each node builded like this:
Code:
typedef struct node node;
struct node {
int value;
node *left,* right,*next;
};
i need to change it into a sorted linked list from the smallest to the biggest.
i cant use malloc
and i cant change the anything in this tree
i need to write a function called
node *tree2list(node *root) that gets a root of the tree and returns the head of a list
first i can find the smallest member in this tree
Code:
while (tree->left){
tree=tree->left;
}
the problem comes when i need to find the second smallest
and put it to the "next" of the smallest member of all the tree
its a recursion
but i dont know how to make a pointer for a tree which will lack that "first found " node
because our pointer after that loop is at the bottom of a tree
i cant go back to the root
and i cant cut this "founded node" from that tree without changing the structure of a tree
??