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  
Share this Question
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 treebuild 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 rightnode
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 leftbranch
goes from BranchLowest to MiddleNode1, and each rightbranch 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+(41))/2=2. The left node for 2 starts at (1+(21))/2=1.
Node 1 is a leaf node. You then process parent node 2. You then
go to the rightbranch for 2, which is leafnode 3. (The right
branch goes from 2+1 to 41, where 2 is your node, and 4 is your
parent's node.) You're now done with the leftnode 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 leafnode 5,
parent node 6, right branch to leafnode 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 singlylinked
list.

++++
 Kenneth J. Brody  www.hvcomputer.com  
 kenbrody/at\spamcop.net  www.fptech.com  #include <std_disclaimer.h> 
++++
Don't email me at: <mailto:Th*************@gmail.com>  
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  
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  
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.  
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.
endwhile
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++faqlite
C Faq: http://www.eskimo.com/~scs/cfaq/top.html
alt.comp.lang.learn.cc++ 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  
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 redblack 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  
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 redblack 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...ancedBST.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. 902908.

"C has its problems, but a language designed from scratch would have some too,
and we know C's problems."
Bjarne Stroustrup  
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 redblack 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...ancedBST.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. 902908.
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  
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 nary
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 redblack 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...ancedBST.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. 902908.
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  
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 singlylinked 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  
P: n/a
 pr********@gmail.com wrote:
[ Don't toppost, 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 nary 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  
P: n/a

**** Rude topposting 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 redblack 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...ancedBST.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. 902908.
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 nary 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  
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...ancedBST.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. 902908.
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  
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 nary 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  
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 nary 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 toppost.
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 nary 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.  
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...ancedBST.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. 902908.
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 nearoptimal. 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  
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.  
P: n/a

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  
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,
EMail: bolsh at gimp dot org
CV: http://dneary.free.fr/CV/  
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 BinarySearch 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 UNIONFIND structure for the updates.
HTH,
Till

Please add "Salt and Peper" to the subject line to bypass my spam filter  
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 BinarySearch 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.  
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 p1;putchar(p[i]\
);}return 0;}  
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.  
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  
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.   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 4543
 replies: 25
 date asked: Nov 14 '05
