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

??

Is using calloc() an option?

i think calloc is forbidden too

its an "in order" traversal
first it goes to the most left (the smallest) then it goes to the middle one
then to the biggest
so my solution is :

Code:

typedef struct node node;
struct node {
  int value;
   node *left,* right,*next;
}; 

node *tree2list(node *root)
    {

 tree2list(root->left);
    if (root){
       return root;
                }
 tree2list(root->left);

}

by this traversal i go from the smallest to the biggest
BUT I DONT KNOW HOW TO DO THE LINKING PART

??

it should be some thing like

tree2list(root->left)->next=tree2list(root);
tree2list(root)->next=tree2list(root)->right;

but i dont know how to combine then in the recurstion
??

Do you ever read the code you write? Or the code you post? Surely you would need to check that root exists before you use it, and doing the left side of the tree twice surely isn't going to help.

So look at what you want to happen -- you need to do the left side, with the least element getting a link from, well, nowhere and the greatest element linking to the root; and you need to do the left side, with the least element getting a link from the root and the greatest element linking to, well, nowhere. You could maybe make the same routine handle this, but it might be nicer to write two slightly different routines; the one on the left would return the greatest element, so it can be linked to root; the one on the right would return the smallest element, so the root can link to it. And if you're going to do the recursion, you should at some point at least try to handle the base case, which in this case is when there is no subtree.

Alright, so I've worked it out on paper. I used a helper function to do the recursion so's I could use some auxiliary variables (namely -- if this element is minimum, what needs to link to here; if this element is maximum, where does this element link to). Again, you're going to know whether you are maximum or minimum based on the absence of children, so those are your base cases, so to speak. If you sit down with a piece of paper and a tree drawn on it, you'll see how what to do in each case, I think.

You'll also need to work out how to return a pointer to the least element in the whole tree (which will become the head of the linked list) (not hard).

If you get stuck, have a hunt here: http://thedailywtf.com
Make sure you have a good go at it first though. I think you're doing well enough that you might be able to get a good solution on your own if you stick at it.

this is an "in order " code
but i need that instead of printing the "value" of the node
it will link it to the "next" of the previous smaller node.

Code:

typedef struct node node;
struct node {
  int value;
   node *left,* right,*next;
}; 

node *tree2list(node *root)
    { 
if (!root){
  return null;
           }
tree2list(root->left);
    if (root){
       printf("%d",root->value);  //i need to change this line 
                }
 tree2list(root->right);
}

the problem is i dont know how to define the recursive call
for the previous node in the list because it can be:

Code:

return tree2list(root->left)->next=*root;

or

Code:

return tree2list(root->right)->next=*root;

i tried to write a new function:
i got to the first stage of the base case.
when i put it into my tree

Code:

http://img204.imageshack.us/my.php?image=19509120rh8.gif

Code:

node tree2list(node *root,node *first,node *last)
{

if (!root->left) {
                  first=root;
                  first->next=last;
                  return last; 
return last=tree2list(root->left,first,root);

in the end when i get to the call where
tree2list(node *root,node *first,node *last) root=node5 first=null last=node10
in this call
first=node5
first->next= node10
and it returns node10

i dont know how to continue
because
i kept only one variable (the last node)
i dont know how to keep the head of the list

and now i got only two nodes connected
i need to connect the last one (which is the local "father") to its right node

i dont know how to do this simple thing
and i cant think further regarding how it will act on the global scale
??

how to develop it further
??

Consider: It's a binary tree. As in all recursive algorithms with a binary tree, you must have two recursive calls in the function (one down the left side, one down the right side). Ask yourself: If this node doesn't have a left child, what does that mean in terms of links? It allows you to set a link (from somewhere to the current node) -- so you'll have to pass in some information to set that link. If this node doesn't have a right child, what does that mean in terms of links? It allows you to set a link (from the current node to somewhere) -- so you'll have to pass in some information to set that link. Every time you make a recursive call you'll change that information for the next level.

You're right that it needs to be in-order based (since you want the links to happen in-order) -- but instead of printing, you need to set a link when the children are NULL. Draw a tree with say ten nodes and look at the pattern. When a node doesn't have a left child, where does the link come from? When a node doesn't have a right child, where does the link go?

i found another solution but i cant understand the purpose of this line

Code:

node* tree2list(node *root) {
  node *head,*temp
if (!root) return null;
if(root->left) head=tree2list(root->left);
else head=root;
temp=head;
while(temp->next) temp=temp->next;
if (head!=root) temp->next=root;               //what is the purpose of this line
root->next=tree2list(root->right);

return head;

What part of "if head is not the same as root, put root on to temp->right" do you struggle to understand?

--
Mats

why does they put this line?

Originally Posted by transgalactic2

why does they put this line?

It sets the link from the largest element on the left to the root element. That's what next is supposed to hold, the link to the next element.

but why to check if head!=root

it should be only temp->next=root;

in order to attach the end of the left sublist point to the root of the tree.

why we need the head!=root
checking?