convert a list to tree

P

prabhat143

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(Node* listHead);

My solution had a lot of scanning and rescanning of list.
regards,
prabhat
 
K

Kenneth Brody

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(Node* listHead);

My solution had a lot of scanning and rescanning of list.

While not strictly a C issue, as it's really an algorithm issue, here
is my solution.


You can do it in only two passes.

The first pass counts the number of nodes.

The second pass is recursive. Start with the number of the middle node,
recursively call the tree-build routine for the left node (which starts
at the middle node of the left branch), create the parent mode for this
piece of the tree, and recursively call it for the right node. (If you
are at a leaf node, then you obviously skip the left- and right-node
steps.)

While this sounds like you need to have random access to the list, it
turns out that all nodes will be found in sequential order. Remember,
until you need the node (ie: it's a leaf node, or it's the parent node
after parsing the left branch), all you need is the node number, not
the contents of the node.

ie:
4
/ \
/ \
/ \
2 6
/ \ / \
1 3 5 7

The MiddleNode is (BranchLowest+BranchHighest)/2. Each left-branch
goes from BranchLowest to MiddleNode-1, and each right-branch goes
from MiddleNode+1 to BranchHighest. If MiddleNode==BranchLowest,
there is no left branch. If MiddleNode==BranchHighest, there is no
right branch. You are at a leaf node when BranchLowest==BranchHighest.

Given 7 nodes, start at node (1+7)/2=4. The left branch for node 4
is at (1+(4-1))/2=2. The left node for 2 starts at (1+(2-1))/2=1.
Node 1 is a leaf node. You then process parent node 2. You then
go to the right-branch for 2, which is leaf-node 3. (The right
branch goes from 2+1 to 4-1, where 2 is your node, and 4 is your
parent's node.) You're now done with the left-node from 4, so you
now have parent node 4. Now you go through the right branch from 4.
You start at node 6, which takes the left branch to leaf-node 5,
parent node 6, right branch to leaf-node 7.

In other words, you have accessed the nodes' contents in order from 1,
2, 3, 4, 5, 6, and finally 7, which is just fine for a singly-linked
list.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>
 
B

Ben Pfaff

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?

How do you want the tree arranged? Do you want a tree or a
binary tree? Also, I think this would be better off in
comp.programming.
 
R

Richard Bos

Given a singly linked, null terminated list, how can it be converted to
tree?

Pop an element off the list, push it into the tree. Repeat until the
list is empty. Preserving the list afterwards is left as an exercise for
the...
What will be the optimal solution?

....homework cheater.

Richard
 
P

prabhat143

I have seen several replies to posts assuming that it's part of
homework and they brand problem poster as "homework cheater". I do
believe that it's true most of time but certainly not true in my case.
There are so many solutions to this problem and I am sure Richard Bos
noticed that I did not ask for the code. I asked for the idea.

Mr. Bos did not even understood the problem. Pop an element of
list...which element of list? Don't you need to scan the list to find
the root of the list? Once you find the root, don't you need to scan
the list again to find it's immediate children? Is there a way the
rescanning could be avoided? That's what I had asked for.
Remember stereotyping is not a good thing.
 
T

Thomas Matthews

I have seen several replies to posts assuming that it's part of
homework and they brand problem poster as "homework cheater". I do
believe that it's true most of time but certainly not true in my case.
There are so many solutions to this problem and I am sure Richard Bos
noticed that I did not ask for the code. I asked for the idea.

Mr. Bos did not even understood the problem. Pop an element of
list...which element of list? Don't you need to scan the list to find
the root of the list? Once you find the root, don't you need to scan
the list again to find it's immediate children? Is there a way the
rescanning could be avoided? That's what I had asked for.
Remember stereotyping is not a good thing.

Very easy. In "popping an element from the list" one removes the
node at the head of the list and the head becomes the next node.
He could have said, "remove the head node of the list" instead.

Here is the algorithm:
while list is not empty do
Set pointer P to head node in list.
Set the pointer to the head node to the link
field of the head node.
Insert node, pointed to by P, into the tree.
end-while

Original issue:
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?

Did I miss something?

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library
 
C

CBFalconer

I have seen several replies to posts assuming that it's part of
homework and they brand problem poster as "homework cheater". I do
believe that it's true most of time but certainly not true in my case.
There are so many solutions to this problem and I am sure Richard Bos
noticed that I did not ask for the code. I asked for the idea.

See my sig for a means of posting acceptable replies via google.
Lack of any context quotations is NOT acceptable.

The simplest method is to scan the list, possibly removing each
scanned item, and insert it in a binary tree. This will require
that the nodes have a spare link available. If the tree is to be
balanced look into AVL and red-black trees, which may require
additional storage fields. Ben Pfaff is an authority on these.
 
B

Ben Pfaff

CBFalconer said:
The simplest method is to scan the list, possibly removing each
scanned item, and insert it in a binary tree. This will require
that the nodes have a spare link available. If the tree is to be
balanced look into AVL and red-black trees, which may require
additional storage fields. Ben Pfaff is an authority on these.

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/libavl.html/Transforming-a-Vine-into-a-Balanced-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.
 
P

prabhat143

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.
 
R

Richard Bos

Mr. Bos did not even understood the problem. Pop an element of
list...which element of list? Don't you need to scan the list to find
the root of the list?

That doesn't even make sense. You cannot scan a singly-linked list to
find its root, since all scans of a SLL proceed _away_ from its root.
Once you find the root, don't you need to scan
the list again to find it's immediate children?

Again, that does not make sense.

If you cannot just pluck a member off the list, then shove it into the
tree, and have it arrive at the right place, then your tree handling
code needs working over.

Richard
 
R

Richard Bos

(e-mail address removed) wrote:

[ Don't top-post, dammit! ]
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.

You're not doing anything to convince me that this is not a homework
question, you know. If this really is a serious problem, you rather
badly need to get that specification tightened up.

Richard
 
C

CBFalconer

**** Rude top-posting fixed ****

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.

Please do NOT top post in technical newsgroups, especially c.l.c.
Your answer belongs after the material to which you reply, or
intermixed with it. First snip any material not germane to your
reply.

Why are you cavilling? You can either sort the list first or do as
I suggested earlier, extract and insert into a binary tree. This
one message already contains several methods.
 
B

Ben Pfaff

Lawrence Kirby said:
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.

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.
 
B

Ben Pfaff

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.

Does the tree need to be a *search* tree? What is the purpose of
the tree?
 
K

Keith Thompson

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.

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).
 
L

Lawrence Kirby

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.

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
 
M

moi

Richard said:
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.programming to the newsgroups.


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
 
D

Dave Neary

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?

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.
 
T

Till Crueger

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?

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
 
R

Richard Harter

Till Crueger seems to be the only person who read the request and
understood it. It's sort of depressing, really.

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(ListNode * 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]

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, (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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,159
Messages
2,570,879
Members
47,414
Latest member
GayleWedel

Latest Threads

Top