convert a list to tree

[prabhat143@gmail.com]

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

[Kenneth Brody]

Re: convert a list to tree

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

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+B ranchHighest)/2. Each left-branch
goes from BranchLowest to MiddleNode-1, and each right-branch goes
from MiddleNode+1 to BranchHighest. If MiddleNode==Bra nchLowest,
there is no left branch. If MiddleNode==Bra nchHighest, there is no
right branch. You are at a leaf node when BranchLowest==B ranchHighest.

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:ThisIsA SpamTrap@gmail. com>

[Ben Pfaff]

Re: convert a list to tree

prabhat143@gmai l.com writes:
[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]

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.programmin g.
--
"I'm not here to convince idiots not to be stupid.
They won't listen anyway."
--Dann Corbit

[Richard Bos]

Re: convert a list to tree

prabhat143@gmai l.com wrote:
[color=blue]
> Given a singly linked, null terminated list, how can it be converted to
> tree?[/color]

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...
[color=blue]
> What will be the optimal solution?[/color]

....homework cheater.

Richard

[prabhat143@gmail.com]

Re: convert a list to tree

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.

[Thomas Matthews]

Re: convert a list to tree

prabhat143@gmai l.com wrote:[color=blue]
> 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.
>[/color]

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:[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]

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.l earn.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

[CBFalconer]

Re: convert a list to tree

prabhat143@gmai l.com wrote:[color=blue]
>
> 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.[/color]

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.c om, 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

[Ben Pfaff]

Re: convert a list to tree

CBFalconer <cbfalconer@yah oo.com> writes:
[color=blue]
> 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.[/color]

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.
--
"C has its problems, but a language designed from scratch would have some too,
and we know C's problems."
--Bjarne Stroustrup

[Lawrence Kirby]

Re: convert a list to tree

On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
[color=blue]
> CBFalconer <cbfalconer@yah oo.com> writes:
>[color=green]
>> 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.[/color]
>
> 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.

I return you now to your normal C service.

Lawrence

[prabhat143@gmail.com]

Re: convert a list to tree

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:[color=blue]
> On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
>[color=green]
> > CBFalconer <cbfalconer@yah oo.com> writes:
> >[color=darkred]
> >> 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.[/color]
> >
> > 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
> >[/color][/color]
http://www.stanford.edu/~blp/avl/lib...anced-BST.html[color=blue][color=green]
> > 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[/color]
list at[color=blue]
> 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[/color]

[Richard Bos]

Re: convert a list to tree

prabhat143@gmai l.com wrote:
[color=blue]
> 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?[/color]

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.
[color=blue]
> Once you find the root, don't you need to scan
> the list again to find it's immediate children?[/color]

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

[Richard Bos]

Re: convert a list to tree

prabhat143@gmai l.com wrote:

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

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

[CBFalconer]

Re: convert a list to tree

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

prabhat143@gmai l.com wrote:[color=blue]
> Lawrence Kirby wrote:[color=green]
>> On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:[color=darkred]
>>> CBFalconer <cbfalconer@yah oo.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.[/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.
>>
>> I return you now to your normal C service.[/color]
>
> 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 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.c om, 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

[Ben Pfaff]

Re: convert a list to tree

Lawrence Kirby <lknews@netacti ve.co.uk> writes:
[color=blue]
> On Tue, 18 Jan 2005 15:46:25 -0800, Ben Pfaff wrote:
>[color=green]
>> 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.
--
"It would be a much better example of undefined behavior
if the behavior were undefined."
--Michael Rubenstein

[Ben Pfaff]

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]

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