# Re: convert a list to tree

From: Richard Harter (cri_at_tiac.net)
Date: 01/22/05

```Date: Sat, 22 Jan 2005 18:15:43 GMT

```

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.

>On Thu, 20 Jan 2005 19:55:32 +0100, moi wrote:
>
>> Richard Harter wrote:
>>> On 18 Jan 2005 07:18:40 -0800, prabhat143@gmail.com wrote:
>
>>>>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?
>>>>

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

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]

>> 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?

Apparently "moi" accidently attached comments to the wrong post.
>
>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.

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.

## Relevant Pages

• Re: convert a list to tree
... the input is a list node and the output is a tree ... contains the tree node addresses. ... list node we look up the tree nodes for the item id and the parent id. ... might have a list of components and subsystems. ...
(comp.programming)
• Why am I getting errors when I want to rebuild the TreeView contro
... tree using this new domain so I pass in the new DNS. ... "foreach (DirectoryEntry child in deContexts.Children)" ... string newDomain = domainName; ... //Tag the 1st Tree Node ...
(microsoft.public.dotnet.security)
• Re: Tree Problem
... > || I'm trying to build a tree structure, and one thing I'm finding I need ... > | for UserSub you are allowed to USE the type definition module, ... What if you made the tree node definition more general so that the same derived type ... pointers could be the equivalent next and previous pointers? ...
(comp.lang.fortran)
• RE: Multi Icon Tree View
... Dim tvw as New TreeView ... // Create a new Tree Node ... >Subject: Multi Icon Tree View ...
(microsoft.public.dotnet.framework.windowsforms.controls)
• RE: Add Child Node to Treeview
... thinking yesterday afternoon that perhaps one way to get a unique strKey is ... into the!Parent section. ... 'Fill Tree ... qryFamTree has my main table joined to a second table by WhoID. ...
(microsoft.public.access.formscoding)