Solved

flatten a tree into an array

Posted on 2009-03-30
21
2,233 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
  • 11
  • 7
  • 3
21 Comments
 
LVL 53

Expert Comment

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

Expert Comment

by:Infinity08
Comment Utility
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
Comment Utility
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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> (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
Comment Utility
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
Comment Utility
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
Comment Utility
And it will allow the program to be called as many times as needed
0
 
LVL 53

Expert Comment

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

Author Comment

by:Johnson_sc
Comment Utility
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
Comment Utility
>> 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
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 

Author Comment

by:Johnson_sc
Comment Utility
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
Comment Utility
>> 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
Comment Utility
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
Comment Utility
or this!!
 a[pos++] = node->data;

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
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
Comment Utility
>> or this!!

Yep :)
0
 
LVL 3

Expert Comment

by:csaint00
Comment Utility
:( what was wrong with my way...
0
 

Author Comment

by:Johnson_sc
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
>> 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 your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.

763 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

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now