convert a list to tree

[Keith Thompson]

Re: convert a list to tree

prabhat143@gmai l.com writes:[color=blue]
> Question is the list says: list is not sorted and it is null
> terminated. By tree, it does not mean a binary tree.It could be n-ary
> tree. Each node in the list knows its ID and its parent ID. The root of
> the resulting tree which could be anywhere in list has its parent ID 0.[/color]

Please don't top-post.

This smells like homework.

What's an "ID", and how is it relevant to the problem?

If the tree doesn't have to be binary, the problem is trivial.
A linked list is already an n-ary tree (n=1).

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Lawrence Kirby]

Re: convert a list to tree

On Wed, 19 Jan 2005 08:30:42 -0800, Ben Pfaff wrote:
[color=blue]
> Lawrence Kirby <lknews@netacti ve.co.uk> writes:
>[color=green]
>> On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
>>[color=darkred]
>>> If you just want to convert a (sorted) linked list to a fully
>>> balanced binary tree, there is a simple algorithm for that which
>>> runs in O(n) time and O(1) additional space. See
>>> http://www.stanford.edu/~blp/avl/lib...anced-BST.html
>>> for an annotated implementation, or the original paper for full
>>> details:
>>> Stout, F. S. and B. L. Warren, "Tree Rebalancing in
>>> Optimal Time and Space", Communications of the ACM 29
>>> (1986), pp. 902-908.[/color]
>>
>> If you have a sorted list and you know the number if items in the list at
>> the start there is a very simple recursive soution to create a
>> balanced plain binary tree.
>>
>> To make a (sub)tree of size N
>>
>> 1. If N is 0 the (sub)tree is empty, return.
>> 2. Make a subtree of size N/2
>> 3. Take the next entry from the list and make it into the root of our
>> (sub)tree
>> 4. Make a subtree of size (N - N/2 - 1)
>> 5. The left and right links of the node in 3. are set to the subtrees
>> created in 2. and 4. respectively.[/color]
>
> Your algorithm requires more additional space (O(lg n)) than
> Stout's (O(1)). Otherwise, yes of course that sort of simple
> recursive algorithm works fine.[/color]

True, OTOH the algorithm is very simple, easy to implement correctly, and
it works with a single pass over the data so it should be near-optimal. It
also works with any type of ordered input sequence, in particular the
singly linked list specified by the OP. You could of course preconstruct a
Vine from the linked list and then balance it but that seems excessive. I
doubt whether O(lg n) additional space is a practical issue, especially
compared to the sizes of the datastructures themselves.

Lawrence

[Richard Harter]

Re: convert a list to tree

On 18 Jan 2005 07:18:40 -0800, prabhat143@gmai l.com wrote:
[color=blue]
>Hi,
>
>Given a singly linked, null terminated list, how can it be converted to
>tree? Each node in the list has three attributes: it's ID, it's parent
>ID and of course, the next node it's pointing to. The parent id of root
>of the tree is 0. The length of list is not known. What will be the
>optimal solution?
>
>Node* convertToTree(N ode* listHead);
>
>My solution had a lot of scanning and rescanning of list.
>regards,
>prabhat[/color]


For some reason everyone seems to misread this request. Each node
contains its own ID (so we can know which node is which) and ITS
PARENT ID, i.e., an identifier of the node's parent in the tree. The
structure of the tree is already specified in the list; the object is
to construct the predefined tree.

The fundamental problem I have with this formulation is that the type
of node required for the tree is different from the type of node in
the linked list. Tree nodes provide links to an indefinitely large
number of children; the described list nodes do not.

I have added comp.programmin g to the newsgroups.


Richard Harter, cri@tiac.net
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.

[moi]

Re: convert a list to tree

Richard Harter wrote:[color=blue]
> On 18 Jan 2005 07:18:40 -0800, prabhat143@gmai l.com wrote:
>
>[color=green]
>>Hi,
>>
>>Given a singly linked, null terminated list, how can it be converted to
>>tree? Each node in the list has three attributes: it's ID, it's parent
>>ID and of course, the next node it's pointing to. The parent id of root
>>of the tree is 0. The length of list is not known. What will be the
>>optimal solution?
>>
>>Node* convertToTree(N ode* listHead);
>>
>>My solution had a lot of scanning and rescanning of list.
>>regards,
>>prabhat[/color]
>
>
>
> For some reason everyone seems to misread this request. Each node
> contains its own ID (so we can know which node is which) and ITS
> PARENT ID, i.e., an identifier of the node's parent in the tree. The
> structure of the tree is already specified in the list; the object is
> to construct the predefined tree.
>
> The fundamental problem I have with this formulation is that the type
> of node required for the tree is different from the type of node in
> the linked list. Tree nodes provide links to an indefinitely large
> number of children; the described list nodes do not.
>
> I have added comp.programmin g to the newsgroups.[/color]


Smells like homework. silly typedef's ...
If sizeof pointer <= sizeof ID, this could be done. (XOR trick ?)
Why would anyone ever store the *parent* ID in a linked list node?

HTH,
AvK

[Dave Neary]

Re: convert a list to tree

Hi,

On 18 Jan 2005 07:18:40 -0800, prabhat143@gmai l.com said:[color=blue]
> Given a singly linked, null terminated list, how can it be converted to
> tree? Each node in the list has three attributes: it's ID, it's parent
> ID and of course, the next node it's pointing to. The parent id of root
> of the tree is 0. The length of list is not known. What will be the
> optimal solution?[/color]

Optimal in what respect? Optimal in time is to return the list
itself (linked lists are trees where the child nodes don't know
about their parent). An O(n) solution is to traverse the tree and
set node->parent to prev_node.

Shouldn't a node know about its child nodes too, though? The way
you have described it, the node only knows about it parent and
the next sibling - you need at least the first child too.

Cheers,
Dave.

--
David Neary,
E-Mail: bolsh at gimp dot org
CV: http://dneary.free.fr/CV/

[Till Crueger]

Re: convert a list to tree

On Thu, 20 Jan 2005 19:55:32 +0100, moi wrote:
[color=blue]
> Richard Harter wrote:[color=green]
>> On 18 Jan 2005 07:18:40 -0800, prabhat143@gmai l.com wrote:[/color][/color]
[color=blue][color=green][color=darkred]
>>>Given a singly linked, null terminated list, how can it be converted to
>>>tree? Each node in the list has three attributes: it's ID, it's parent
>>>ID and of course, the next node it's pointing to. The parent id of root
>>>of the tree is 0. The length of list is not known. What will be the
>>>optimal solution?
>>>
>>>Node* convertToTree(N ode* listHead);[/color][/color][/color]
[color=blue][color=green]
>> For some reason everyone seems to misread this request. Each node
>> contains its own ID (so we can know which node is which) and ITS
>> PARENT ID, i.e., an identifier of the node's parent in the tree. The
>> structure of the tree is already specified in the list; the object is
>> to construct the predefined tree.
>>
>> The fundamental problem I have with this formulation is that the type
>> of node required for the tree is different from the type of node in
>> the linked list. Tree nodes provide links to an indefinitely large
>> number of children; the described list nodes do not.
>>
>> I have added comp.programmin g to the newsgroups.[/color]
>
> Smells like homework. silly typedef's ...
> If sizeof pointer <= sizeof ID, this could be done. (XOR trick ?)
> Why would anyone ever store the *parent* ID in a linked list node?[/color]

As far as I understood it the Parent ID is not the ID of the Parent in
the list, but the ID of the Parent in the Tree. So it makes sense actually
to store it. Here is an Example of how it might look:

------- ------- ------- -------
|ID =1| |Id =0| |ID =3| |ID=2 |
|Data | ->|Data | ->|Data | ->|Data |
|PID=0| |PID=0| |PID=0| |PID=1|
------- ------- ------- -------

The tree constructed from this would look like this (Only IDs)

0
/ \
1 3
/
2

There Never was a word about anything being sorted in this case, Nor did
the OP ever talk about an Binary-Search tree. My guess is that the list is
some weird serialisation of the Tree.

To find an O(n^2) Solution to this problem is quiet trivial. I am not sure
if there actually is a better solution. I certainly can't think of one. My
best guess would be to begin with a forest instead of a tree, i.E.
something like this:

While (Nodes in List) DO
Pop a node from the list
Create a new Tree in the Forest from node
Combine trees
OD

The only Problem I have left is the Combine Trees step, which might get
pretty lengthy. I guess each tree has to keep a List of its Parent, and
you`d have to Use some kind of UNION-FIND structure for the updates.

HTH,
Till

--
Please add "Salt and Peper" to the subject line to bypass my spam filter

[Richard Harter]

Re: convert a list to tree

On Sat, 22 Jan 2005 11:36:56 +0100, Till Crueger <TillFC@gmx.net >
wrote:

Till Crueger seems to be the only person who read the request and
understood it. It's sort of depressing, really.
[color=blue]
>On Thu, 20 Jan 2005 19:55:32 +0100, moi wrote:
>[color=green]
>> Richard Harter wrote:[color=darkred]
>>> On 18 Jan 2005 07:18:40 -0800, prabhat143@gmai l.com wrote:[/color][/color]
>[color=green][color=darkred]
>>>>Given a singly linked, null terminated list, how can it be converted to
>>>>tree? Each node in the list has three attributes: it's ID, it's parent
>>>>ID and of course, the next node it's pointing to. The parent id of root
>>>>of the tree is 0. The length of list is not known. What will be the
>>>>optimal solution?
>>>>
>>>>Node* convertToTree(N ode* listHead);[/color][/color][/color]

This can't be right; the input is a list node and the output is a tree
node. A proper description might be:

TreeNode * convertToTree(L istNode * ListHead);

There are various structures that one could use for a tree node; a
reasonable (minimal) choice is:

struct TreeNode {
ID id;
TreeNode *children;
};

The natural way to do this task is O(n^2). The key difficulty is
associating an id with an address, i.e., a list node specifies a
parent's id whereas what one needs is the address of the parent's node
in the tree.

Realizing that, the obvious thing to do is to use a hash table that
contains the tree node addresses. Initially each tree node contains
an id and an empty children list. We then scan the list; for each
list node we look up the tree nodes for the item id and the parent id.
We then add the item tree node to the parent tree node's children
list. This is a O(n) solution. There are many others, both O(n) and
O(n*log(n)).

[snip complaint by RH]
[color=blue][color=green]
>> Smells like homework. silly typedef's ...
>> If sizeof pointer <= sizeof ID, this could be done. (XOR trick ?)
>> Why would anyone ever store the *parent* ID in a linked list node?[/color][/color]

Apparently "moi" accidently attached comments to the wrong post.[color=blue]
>
>As far as I understood it the Parent ID is not the ID of the Parent in
>the list, but the ID of the Parent in the Tree. So it makes sense actually
>to store it. Here is an Example of how it might look:
>
>------- ------- ------- -------
>|ID =1| |Id =0| |ID =3| |ID=2 |
>|Data | ->|Data | ->|Data | ->|Data |
>|PID=0| |PID=0| |PID=0| |PID=1|
>------- ------- ------- -------
>
>The tree constructed from this would look like this (Only IDs)
>
> 0
> / \
> 1 3
> /
> 2
>
>There Never was a word about anything being sorted in this case, Nor did
>the OP ever talk about an Binary-Search tree. My guess is that the list is
>some weird serialisation of the Tree.[/color]

I can think of contexts where it would be a natural data
representation. For example, given a company you might a have a list
of employees (specified by ID) and, for each employee, the ID of their
boss. What you want is the command structure of the company. You
might have a list of components and subsystems. For each element you
have know the subsystem it belongs to; recover the the system
structure.


Richard Harter, cri@tiac.net
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.

[Ben Pfaff]

Re: convert a list to tree

cri@tiac.net (Richard Harter) writes:
[color=blue][color=green][color=darkred]
>>>>>Node* convertToTree(N ode* listHead);[/color][/color]
>
> This can't be right; the input is a list node and the output is a tree
> node.[/color]

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.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Richard Harter]

Re: convert a list to tree

On Sat, 22 Jan 2005 10:26:32 -0800, Ben Pfaff <blp@cs.stanfor d.edu>
wrote:
[color=blue]
>cri@tiac.net (Richard Harter) writes:
>[color=green][color=darkred]
>>>>>>Node* convertToTree(N ode* listHead);[/color]
>>
>> This can't be right; the input is a list node and the output is a tree
>> node.[/color]
>
>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
>representati on of a tree.[/color]

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, cri@tiac.net
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@gmail.com]

Re: convert a list to tree

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_arra y, 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]

Re: convert a list to tree

On 24 Jan 2005 07:01:49 -0800, prabhat143@gmai l.com wrote:

[snip]
[color=blue]
>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.[/color]

You're welcome.
[color=blue]
>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.[/color]

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



Richard Harter, cri@tiac.net
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.