By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,272 Members | 1,272 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,272 IT Pros & Developers. It's quick & easy.

convert a list to tree

P: n/a
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

Nov 14 '05 #1
Share this Question
Share on Google+
25 Replies


P: n/a
pr********@gmail.com wrote:

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:Th*************@gmail.com>

Nov 14 '05 #2

P: n/a
pr********@gmail.com writes:
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.
--
"I'm not here to convince idiots not to be stupid.
They won't listen anyway."
--Dann Corbit
Nov 14 '05 #3

P: n/a
pr********@gmail.com wrote:
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
Nov 14 '05 #4

P: n/a
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.

Nov 14 '05 #5

P: n/a
pr********@gmail.com wrote:
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

Nov 14 '05 #6

P: n/a
pr********@gmail.com wrote:

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.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #7

P: n/a
CBFalconer <cb********@yahoo.com> writes:
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/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.
--
"C has its problems, but a language designed from scratch would have some too,
and we know C's problems."
--Bjarne Stroustrup
Nov 14 '05 #8

P: n/a
On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
CBFalconer <cb********@yahoo.com> writes:
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/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.


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.

I return you now to your normal C service.

Lawrence

Nov 14 '05 #9

P: n/a
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.
Lawrence Kirby wrote:
On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
CBFalconer <cb********@yahoo.com> writes:
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/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.


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.

I return you now to your normal C service.

Lawrence


Nov 14 '05 #10

P: n/a
pr********@gmail.com wrote:
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
Nov 14 '05 #11

P: n/a
pr********@gmail.com 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
Nov 14 '05 #12

P: n/a
**** Rude top-posting fixed ****

pr********@gmail.com wrote:
Lawrence Kirby wrote:
On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
CBFalconer <cb********@yahoo.com> writes:

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 (beware wrap)

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.


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.

I return you now to your normal C service.


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.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #13

P: n/a
Lawrence Kirby <lk****@netactive.co.uk> writes:
On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
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.


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.
--
"It would be a much better example of undefined behavior
if the behavior were undefined."
--Michael Rubenstein
Nov 14 '05 #14

P: n/a
pr********@gmail.com writes:
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?
--
"The expression isn't unclear *at all* and only an expert could actually
have doubts about it"
--Dan Pop
Nov 14 '05 #15

P: n/a
pr********@gmail.com writes:
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).

--
Keith Thompson (The_Other_Keith) ks***@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.
Nov 14 '05 #16

P: n/a
On Wed, 19 Jan 2005 08:30:42 -0800, Ben Pfaff wrote:
Lawrence Kirby <lk****@netactive.co.uk> writes:
On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
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.


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.


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

Nov 14 '05 #17

P: n/a
On 18 Jan 2005 07:18:40 -0800, pr********@gmail.com wrote:
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

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.
Richard Harter, cr*@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.
Nov 14 '05 #18

P: n/a
moi
Richard Harter wrote:
On 18 Jan 2005 07:18:40 -0800, pr********@gmail.com wrote:

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


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
Nov 14 '05 #19

P: n/a
Hi,

On 18 Jan 2005 07:18:40 -0800, pr********@gmail.com said:
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.

--
David Neary,
E-Mail: bolsh at gimp dot org
CV: http://dneary.free.fr/CV/
Nov 14 '05 #20

P: n/a
On Thu, 20 Jan 2005 19:55:32 +0100, moi wrote:
Richard Harter wrote:
On 18 Jan 2005 07:18:40 -0800, pr********@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?

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


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

Nov 14 '05 #21

P: n/a
On Sat, 22 Jan 2005 11:36:56 +0100, Till Crueger <Ti****@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, pr********@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?

Node* convertToTree(Node* listHead);

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]
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, cr*@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.
Nov 14 '05 #22

P: n/a
cr*@tiac.net (Richard Harter) writes:
>Node* convertToTree(Node* listHead);


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.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 14 '05 #23

P: n/a
On Sat, 22 Jan 2005 10:26:32 -0800, Ben Pfaff <bl*@cs.stanford.edu>
wrote:
cr*@tiac.net (Richard Harter) writes:
>>Node* convertToTree(Node* listHead);


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.


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, cr*@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.
Nov 14 '05 #24

P: n/a
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

Nov 14 '05 #25

P: n/a
On 24 Jan 2005 07:01:49 -0800, pr********@gmail.com 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, cr*@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.
Nov 14 '05 #26

This discussion thread is closed

Replies have been disabled for this discussion.