Solved

flatten a tree into an array

Posted on 2009-03-30
21
2,263 Views
Last Modified: 2013-12-14
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
Comment
Question by:Johnson_sc
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 11
  • 7
  • 3
21 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 24018678
If you make pos static (so each recursive call uses the same value), it should work better.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24018695
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
 

Author Comment

by:Johnson_sc
ID: 24018774
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
Independent Software Vendors: 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!

 
LVL 53

Expert Comment

by:Infinity08
ID: 24018800
>> (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
 
LVL 3

Expert Comment

by:csaint00
ID: 24018802
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 24018807
But remember that this is really a non-solution for the reason I explained in my second post (http:#24018695) above.
0
 
LVL 3

Expert Comment

by:csaint00
ID: 24018822
And it will allow the program to be called as many times as needed
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24018868
csaint00 : come on, don't deprive Johnson_sc of the learning experience of finding his own solution :)
0
 

Author Comment

by:Johnson_sc
ID: 24019144
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 24019194
>> 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
 

Author Comment

by:Johnson_sc
ID: 24019298
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 24019339
>> 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
 

Author Comment

by:Johnson_sc
ID: 24019427
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
 

Author Comment

by:Johnson_sc
ID: 24019445
or this!!
 a[pos++] = node->data;

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24019450
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
 
LVL 53

Accepted Solution

by:
Infinity08 earned 125 total points
ID: 24019461
>> or this!!

Yep :)
0
 
LVL 3

Expert Comment

by:csaint00
ID: 24019505
:( what was wrong with my way...
0
 

Author Comment

by:Johnson_sc
ID: 24019552
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 24019599
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
 

Author Comment

by:Johnson_sc
ID: 24019664
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 24019715
>> 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

Industry Leaders: 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!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Jaspersoft Studio is a plugin for Eclipse that lets you create reports from a datasource.  In this article, we'll go over creating a report from a default template and setting up a datasource that connects to your database.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question