• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2324
  • Last Modified:

flatten a tree into an array

Hi,

I wrote a code in order to flatten a binary tree into an array. I'm not sure if it's correct because I've looked others implementation in some websites and its look different.

I'm trying to use the in-order approach, once I want the elements sorted.

thanks for pointing out mistakes!
void flatten(node *node, int a[]){
int pos = 0;
 
    if(node){
        flatten(node->pleft,a);
        a[pos++] = node->data;
        flatten(node->pright,a);
      }
}

Open in new window

0
Johnson_sc
Asked:
Johnson_sc
  • 11
  • 7
  • 3
1 Solution
 
Infinity08Commented:
If you make pos static (so each recursive call uses the same value), it should work better.
0
 
Infinity08Commented:
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.
0
 
Johnson_scAuthor Commented:
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!
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
Infinity08Commented:
>> (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);
    }
}

Open in new window

0
 
csaint00Commented:
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);
      }
}

Open in new window

0
 
Infinity08Commented:
But remember that this is really a non-solution for the reason I explained in my second post (http:#24018695) above.
0
 
csaint00Commented:
And it will allow the program to be called as many times as needed
0
 
Infinity08Commented:
csaint00 : come on, don't deprive Johnson_sc of the learning experience of finding his own solution :)
0
 
Johnson_scAuthor Commented:
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
      }
}

Open in new window

0
 
Infinity08Commented:
>> 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 }
0
 
Johnson_scAuthor Commented:
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;
}

Open in new window

0
 
Infinity08Commented:
>> 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).
0
 
Johnson_scAuthor Commented:
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;
}

Open in new window

0
 
Johnson_scAuthor Commented:
or this!!
 a[pos++] = node->data;

Open in new window

0
 
Infinity08Commented:
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).
0
 
Infinity08Commented:
>> or this!!

Yep :)
0
 
csaint00Commented:
:( what was wrong with my way...
0
 
Johnson_scAuthor Commented:
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!
0
 
Infinity08Commented:
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 :)
0
 
Johnson_scAuthor Commented:
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
0
 
Infinity08Commented:
>> 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).
0

Featured Post

How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

  • 11
  • 7
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now