convert a list to tree

[Ben Pfaff]

This can't be right; the input is a list node and the output is a tree
node.

If the node has appropriate fields for representing both lists
and trees, then it could be correct. For example, you could
represent a list with `prev' and `next' pointers, then later
treat these as `left' and `right' pointers in a binary tree
representation of a tree.

 

[Richard Harter]

If the node has appropriate fields for representing both lists
and trees, then it could be correct. For example, you could
represent a list with `prev' and `next' pointers, then later
treat these as `left' and `right' pointers in a binary tree
representation of a tree.

True enough. However the OP explicitly said that (a) the nodes
contained two IDs and one pointer, and (b) the tree isn't necessarily
a binary tree, so one couldn't reuse the nodes the way you suggest.

On the other hand my remark about a tree node needing one pointer is
also wrong; you need a children link and a sibling link. If we add
another link field then your suggestion goes through.



Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.

 

[prabhat143]

I am the one who wrote OP. Finally, people understood my question. It's
always easy to assume the tree is "binary" whenever we talk about tree.
The nodes of list in problem look like this:

struct Object {
// THESE FIELDS ARE ALREADY DEFINED; YOU MAY NOT MODIFY THEM
Object* next_ptr; // Next object in list; NULL if end of
list.
unsigned int ID; // unique identifier for this object.
unsigned int parent_ID; // 0, if object is root of tree.

// THESE FIELDS REPRESENT THE TREE WHICH NEED TO BE FILLED
Object* parent_ptr; // Initialized as NULL.
unsigned int child_count; // Initialized as 0.
Object** child_ptr_array; // Initialized as NULL.
} ;
Need to implement the method:
Object* convert_List_To_Tree (Object* list_head);

By optimal I meant the solution that requires the least number of
scanning of list nodes with least extra space. My solution had one
scanning to find root which is O(n) in the worst case, another to count
number of children for a particulr node so that you know the value for
child_count and can initialize child_ptr_arry accordingly and then you
fill child_ptr_array. To fill child_ptry_array, I had two choices: one
to maintain a seperate list of children as I find child_count for a
particular node and put these nodes in child_ptr_array OR rescan the
list with num_children as counter. In rescanning of the list, I dint
start from the head but from the last node that I visited.

I wanted to see a better solution if it exists and of course some
analysis from you smart people. Thanks to you all with a special thanks
to Mr. Crueger and Mr.Harter.

By the way, I ran into this problem during one job interview. If it
makes you feel better, pls free to "brand" it as a homework problem.
cheers,
prabhat

 

[Richard Harter]

On 24 Jan 2005 07:01:49 -0800, (e-mail address removed) wrote:

[snip]

I wanted to see a better solution if it exists and of course some
analysis from you smart people. Thanks to you all with a special thanks
to Mr. Crueger and Mr.Harter.

You're welcome.

By the way, I ran into this problem during one job interview. If it
makes you feel better, pls free to "brand" it as a homework problem.

You should have said that it was a job interview question originally.
That would have saved a lot of confusion.



Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.