# Changing a tree into a list question

1. Oct 30, 2008

### transgalactic

i got a BST tree
each node builded like this:
Code (Text):

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 (Text):

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

??

2. Nov 1, 2008

### transgalactic

by "in order" traversal method
it goes from the smallest to the biggest
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 (Text):

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
??

3. Nov 1, 2008

### Coin

So first off, this:

Is *really bad*, it will cause an immediate infinite loop. There needs to be some kind of "termination condition" that will cause tree2list to NOT be called when you reach the leftmost place.

As for "how to combine them in the recursion", I am not altogether certain I understand what you are trying to do, but what I would recommend is that you add a second argument to tree2list pointing to the list you are trying to add to, and then you simply add nodes to the list pointed to as you go. (If that makes sense.)

Another option is to write some kind of separate "concatenate linked lists" function. If you have the ability to add one linked list to another, then your tree2list function becomes very simple, something like :

list l = tree2list(root->left)
list r = tree2list(root->right)
return list_concatenate(l, r)

4. Nov 4, 2008

### transgalactic

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 (Text):

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 (Text):

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

or
Code (Text):

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

??

5. Nov 5, 2008

### Coin

I'm sorry, I just don't understand what it is you're trying to do here. I guess I can make two general comments about your particular code snippets here:

- You say "if (!root) return null;", then a few lines later you say "if (root) { do something }". The second if (root) is redundant because if root is null, then you have already returned from the function. Remember, if you "return" at any point during a function then the remainder of the function is not executed.

- If you say something->next=*root; this will not compile. "->next" and "root" are pointers to nodes, "*root" will be just a node. The types do not match.

- If you remove the asterisk and say " return tree2list(root->left)->next=root; " this will compile but I do not think it will do what you want. This will:
- Query tree2list to obtain a pointer to [some node]
- Assign the 'next' field of [some node] to root
- Throw the pointer to [some node] away and return root
Sometimes it is a good idea to try to only do one thing per line, so that you do not create confusions like this.

6. Nov 8, 2008

### transgalactic

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 (Text):

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

Code (Text):

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
??