flatten a tree into an array

If you make pos static (so each recursive call uses the same value), it should work better.

Remember that the function can only be called once this way, since you have no way to re-set pos to 0. You should probably look for a different way of making pos available to all levels.

ok, but if I'm coding in C, how can I turn it static? (I thought it already would be static, for default).

thanks infinity!

>> (I thought it already would be static, for default).

I'm talking about the 'static' keyword, not about statically vs. dynamically allocated memory.

You're right that pos is statically allocated. But the 'static' keyword does something else : it creates only one instance of the variable in question, which is used by all of the 'flatten' function calls (whether nested or not).

void flatten(node *node, int a[]){
    static int pos = 0;
 
    if(node){
        flatten(node->pleft,a);
        a[pos++] = node->data;
        flatten(node->pright,a);
    }
}

Select allOpen in new window

Quick and dirty way would be to create another function to use instead of flatten, usually flattenHelper.
Attached code is untested but it should give you a general idea.

void flatten(node *node, int a[]){
  int pos = 0;
  flattenHelper(node, a, &pos);
 
}
 
void flattenHelper(node *node, int a[], int *pos){
    if(node){
        flattenHelper(node->pleft,a, pos);
        a[(*pos)++] = node->data;
        flattenHelper(node->pright,a, pos);
      }
}

Select allOpen in new window

But remember that this is really a non-solution for the reason I explained in my second post (http:#24018695) above.

And it will allow the program to be called as many times as needed

csaint00 : come on, don't deprive Johnson_sc of the learning experience of finding his own solution :)

thanks csaint00, I have a clear idea to fix it...

What about this one here guys:

thanks all

void flatten(node *node, int a[], int pos){
int pos;
 
    if(node == NULL)
    return pos;   // pos get the position of the last node
 
    pos = flatten(node->pleft,a, pos);  //go to left subtree until null
    a[pos] = node->data;           //write in the array at the position
    pos = flatten(node->pright,a, pos); // go to right subtree
      }
}

Select allOpen in new window

>> What about this one here guys:

1) pos never gets incremented.

2) you also want to return something at the end of the function (ie. not only if node == NULL)

3) the local int pos; should not be there

4) there's an extra }

ops! right on! I'm struggling in the algorithm and forgot he details

ok, I just didn't understand about this increment... why? To my mind, I'll get the position of the last node (without children) and return this position to the array... So, each time I get a position, it will be different from another, because each node has a position different in the memory..

Therefore, why should I increment if each pos has a different value?

ps. I'm sorry if I didn't express my idea clearly.

int flatten(node *node, int a[], int pos){
 
    if(node == NULL)
    return pos;   
 
    pos = flatten(node->pleft,a, pos);  
    a[pos] = node->data;           
    pos = flatten(node->pright,a, pos); 
    
    return pos;
}

Select allOpen in new window

>> Therefore, why should I increment if each pos has a different value?

If you initially set pos to 0 (on the first call to 'flatten'), then that value (0) will be passed to each recursive call as third argument, and will be returned when the function ends. Nowhere during all this, will the value be changed, so it will always be 0.

In other words, all data will be written to position 0 in the array (overwriting the previously written data).

yes, your are right, thanks. So, what about increment when I am passing the arguments? like this:

int flatten(node *node, int a[], int pos){
 
    if(node == NULL)
    return pos;   
 
    pos = flatten(node->pleft,a, pos + 1); //a[0] would be lost, so starts in a[1]
    a[pos] = node->data;           
    pos = flatten(node->pright,a, pos + 1); 
    
    return pos;
}

Select allOpen in new window

or this!!

 a[pos++] = node->data;

Select allOpen in new window

You don't want to increment pos each time you recursively call 'flatten'.
You only want to inrement it when you need to move to the next position in the array - ie. just after you wrote a value to the current position in the array (refer to your original code where that was done correctly).

:( what was wrong with my way...

man, programming is so exciting!!!
thanks Infinity08, one less question to solve, let's keep going!


hey csaint00, I think your code simply 'beautiful', very classic, well done and clear, neat solution! I learned with your fashion but I'd wanted to fix my ugly and messed up code!

thanks experts!

I wouldn't have minded if you gave csaint00 some or all of the points ;) If it was useful to you, then it's worth assigning points to it :)

just one last question:

if I say:

if(node == NULL)
    return pos;

it wouldn't return the node with the null adress???

 I mean, the correct shouldn't be???
if((node->pleft) == NULL)
    return pos;

because if I am at node == NULL, how I will return back to the node above??
am I clear?

thanks

>> because if I am at node == NULL, how I will return back to the node above??

That's where the recursive calls come in handy.
Calling the function recursively, moves one level down in the tree (either left or right).
Retruning from the function, moves one level up in the tree.

This also works if node == NULL, because returning goes back to the previous stack frame, which still has node set to the good position (one level up).