Simple question for those who understand recursion well. Please help.

[success_ny]

I have a tree represented as a linked list of simple objects
(nodeId/parentId pairs) where the root node is the 1st element in the
list. The other nodes are in somewhat random order. The parentId refers
to the parent node.

I want to convert it into a list where the values are in pre-order.
I.e., I want to get this list as follows: ABCDEFGHIJ (see graph below).
I.e., get the 1st node, put in in the list. If it has children, go
through them one by one, get their child nodes, then put the parent in
the list, then the leftmost first, and go from there. I.e., so that
it's ordered in my linked list like this by (letters represent nodeId):


A
/ \
B J
/ | \
C H I
|
D
/|\
E F G

I created the following recursive method but it does not work
correctly. For example, it places the nodes A then B and then J into
the list first, rather than getting to J after adding all the child
nodes. "isOnTheList" checkes whether the item is already in the list.
"getImmediateChildren" returns the list of immediate child nodes
ordered by nodeId

Note: the empty list is passed to the method and is populated with the
result:

public static void orderTree(List list, List treeList) {
if(treeList == null || treeList.size() == 0)
return;

Node child = null; List children = null;

for(int i = 0; i < treeList.size(); i++) {
node = (Node) treeList.get(i);
// get list of children for this node
children = getImmediateChildren(node, treeList);

// if the node is not yet on the list, add it
if(! isOnTheList(node, list) )
list.add(cat);

// if it has children, recurse to add all other nodes
if(children.size() > 0) {
orderTree(list, children);
}
}
}

Any idea what the problem is?

Thanks.

 

[pkriens]

The code is not complete ... Can't see what you are adding to the
result list, i.e. list.add(cat). That variable is not declared as far
as I can see.

I am also not clear why you check for duplicates? This can have
unexpected side effects.

You also check for an empty set of children twice.

One thing you should do with recursion is to separate the "unary" case
from the "multiple' case. This code should work and is imho clearer for
a depth first collection:

void order( Node node, List result ) {
result.add( node );
for ( Iterator i=node.getChildren().iterator(); i.hasNext(); )
order( (Node) i.next(), result );
}

 

[Patrick May]

public static void orderTree(List list, List treeList) {
if(treeList == null || treeList.size() == 0)
return;

Node child = null; List children = null;

for(int i = 0; i < treeList.size(); i++) {
node = (Node) treeList.get(i);
// get list of children for this node
children = getImmediateChildren(node, treeList);

// if the node is not yet on the list, add it
if(! isOnTheList(node, list) )
list.add(cat);

// if it has children, recurse to add all other nodes
if(children.size() > 0) {
orderTree(list, children);
}
}
}

Any idea what the problem is?

When building a recursive solution, you must clearly identify
your termination condition. You haven't done that here.

Leaving aside the fact that your code snippet won't compile and
the questionable use of a static method, I believe your immediate
problem is that your recursive call to orderTree() is being passed a
subset of the full treeList that probably doesn't have the children of
B in it. Add some logging or step through it with a debugger to
confirm or disprove that hypothesis.

I suggest rewriting this to pass in a start node along with the
full collection of nodes. That will make it a lot easier to identify
your recursion termination condition.

Regards,

Patrick

 

[Patrick May]

I suggest rewriting this to pass in a start node along with the
full collection of nodes. That will make it a lot easier to
identify your recursion termination condition.

Re-reading this, I don't think I was very clear. Here's an
example based on your code. If I were writing it from scratch, I'd
probably think in terms of operations on a Tree class.

import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;

public class TreeWalker
{
public TreeWalker()
{
} // end TreeWalker::TreeWalker()


public static List<Node> getImmediateChildren(Node node,List<Node> treeList)
{
LinkedList<Node> children = new LinkedList<Node>();
ListIterator<Node> it = treeList.listIterator(0);

Node current;
while (it.hasNext())
{
current = it.next();
if (node.name().equals(current.parent()))
children.add(current);
}

return children;
} // end TreeWalker::getImmediateChildren(Node,List)


public static List<String> orderTree(Node startNode,List<Node> treeList)
{
LinkedList<String> resultList = new LinkedList<String>();

if ((startNode != null) && (treeList != null))
{
// add the node to the result list (ignore possibility of cycles)
resultList.add(startNode.name());

// get list of children for this node
List<Node> children = getImmediateChildren(startNode,treeList);

// if it has children, recurse to add all other nodes
ListIterator<Node> it = children.listIterator();
while (it.hasNext())
resultList.addAll(orderTree(it.next(),treeList));
}

return resultList;
} // end TreeWalker:rderTree(List,List)


public static void main(String args[])
{
// construct the tree
Node a = new Node("A",null);
Node b = new Node("B","A");
Node c = new Node("C","B");
Node d = new Node("D","C");
Node e = new Node("E","D");
Node f = new Node("F","D");
Node g = new Node("G","D");
Node h = new Node("H","B");
Node i = new Node("I","B");
Node j = new Node("J","A");

LinkedList<Node> treeNodes = new LinkedList<Node>();
treeNodes.add(a);
treeNodes.add(b);
treeNodes.add(c);
treeNodes.add(d);
treeNodes.add(e);
treeNodes.add(f);
treeNodes.add(g);
treeNodes.add(h);
treeNodes.add(i);
treeNodes.add(j);

List resultList = orderTree(a,treeNodes);
Iterator it = resultList.iterator();
while (it.hasNext())
System.out.println(it.next());
} // end TreeWalker::main(String[])
} // end TreeWalker

The Node class is very simple for this example:

public class Node
{
private String name_ = null;
private String parent_ = null;

public Node(String name,String parent)
{
name_ = name;
parent_ = parent;
} // end Node::Node(String,String)

public String name() { return name_; }
public String parent() { return parent_; }
} // end Node

Regards,

Patrick

 

[success_ny]

Sorry, I made a minor mistake in the original code (where it sais
list.add(cat) it should say list.add(node)

Here is the corrected code sample:

public static void orderTree(List list, List treeList) {
if(treeList == null || treeList.size() == 0)
return;

Node child = null; List children = null;

for(int i = 0; i < treeList.size(); i++) {
node = (Node) treeList.get(i);
// get list of children for this node
children = getImmediateChildren(node, treeList);

// if the node is not yet on the list, add it
if(! isOnTheList(node, list) )
list.add(node);

// if it has children, recurse to add all other nodes
if(children.size() > 0) {
orderTree(list, children);
}
}
}

1) The nodes in the list are connect by parentId. So all elements are a
list of paris where the 2nd element points to a parent. There are no
orphan nodes. I can get a list of child nodes in order. I.e.,
getImmediateChildren(A) will return B,J

 

[Andrew Thompson]

Sorry, I made a minor mistake in the original code ..

I have one word for you. OK, five words in one acronym.

SSCCE <http://www.physci.org/codes/sscce.jsp>

 

[Patrick May]

children = getImmediateChildren(node, treeList); [ . . . ]
if(children.size() > 0) {
orderTree(list, children); [ . . . ]
1) The nodes in the list are connect by parentId. So all elements
are a list of paris where the 2nd element points to a parent. There
are no orphan nodes. I can get a list of child nodes in order. I.e.,
getImmediateChildren(A) will return B,J

That confirms my previous suspicion. You initially call the
method with (A ((B (C (H I J) D) E F) J)), or similar, then recurse
passing only (B J). That explains the behavior you're seeing.

Regards,

Patrick

 

[success_ny]

Andrew Thompson: Do you have any other advice for me? Because I really
feel like you can enrich my mind with your opinions on that kind of
questions I should ask. Don't feel compelled to write anything in
responce, especially if you have nothing relevant to say on the
subject...

 

[Andrew Thompson]

Andrew Thompson: Do you have any other advice for me?

The implied words you apparently missed..

"Prepare an.."
<http://groups.google.com.au/group/comp.lang.java.programmer/msg/4308df558d9739f9>
"..to assist those trying to help you."

Most of those other ("quoted") words were in the
document to which I linked from that thread.

Did you read it?


Of course, since Patrick has apparently sorted your problem,
it is no longer relevant to this thread, but you might keep
it in mind for next time.

HTH

 

[Mike Schilling]

The implied words you apparently missed..

"Prepare an.."
<http://groups.google.com.au/group/comp.lang.java.programmer/msg/4308df558d9739f9>
"..to assist those trying to help you."

Most of those other ("quoted") words were in the
document to which I linked from that thread.

Did you read it?

I just did; it's quite good. I'd add one thing, which is perhaps tangential
to the process of creating a good example, but still quite important:

If your example results in an error message: INCLUDE ALL OF IT! So often
you see things like "There's an error message" or "An exception gets
thrown, I don't know why", or "I get a null pointer exception", but the
stack trace is left out. Which leads to one more point:

If you post both code and output, make sure it's the same code that
generated the output. Sometimes it's clearly not the same (e.g. one of the
lines in a stack trace is a comment) but often it's more frustrating than
that.

 

[Andrew Thompson]

On Sun,28 Aug 2005 07:18:08 GMT, Mike Schilling wrote:

(..re reading SSCCE doc.)

I just did; it's quite good. I'd add one thing, which is perhaps tangential
to the process of creating a good example, but still quite important:

If your example results in an error message: INCLUDE ALL OF IT! So often
you see things like "There's an error message" or "An exception gets
thrown, I don't know why", or "I get a null pointer exception", but the
stack trace is left out. Which leads to one more point:

Good point, but I had so much to say on error messages[1]
and stack traces[2] that each made an entry in the PhySci
Java FAQ itself.

[1] <http://www.physci.org/codes/javafaq.jsp#exact>

If you post both code and output, make sure it's the same code that
generated the output. Sometimes it's clearly not the same (e.g. one of the
lines in a stack trace is a comment) ...

LOL! That would be frustrating!

but.. if I can just get people to post SSCCEs
that do not swallow exceptions, I'll *then*
concentrate on reminding people to post exact
stacktraces* that come from the code of that
minute.

* I am a bit wary of suggesting people post an
entire 1200 line stack trace. Most stacktraces
can be trimmed of all lines referring to java.*
classes (that are not directly mentioned in the
first line)..

When I am looking at a stack trace, I usually skip
over the lines mentioning core classes, which, 99.7%*
of the time, are not directly relevant to the problem.

* Of course, 84.3% of statistics are made up on the spot.

--
Andrew Thompson
physci.org 1point1c.org javasaver.com lensescapes.com athompson.info
"Don't just take me for tryin' to be heavy. Understand, it's time to get
ready.."
Stevie Ray Vaughan and Double Trouble 'Couldn't Stand The Weather'

 

[Mike Schilling]

* I am a bit wary of suggesting people post an
entire 1200 line stack trace. Most stacktraces
can be trimmed of all lines referring to java.*
classes (that are not directly mentioned in the
first line)..

When I am looking at a stack trace, I usually skip
over the lines mentioning core classes, which, 99.7%*
of the time, are not directly relevant to the problem.

* Of course, 84.3% of statistics are made up on the spot.

Sure, but in general it's much easier to skip over irrelevant lines than to
divine the content of lines removed by someone trying to spare you.from that
task. So I prefer that people err on the side of providing more
information.

 

[Virgil Green]

Andrew Thompson: Do you have any other advice for me? Because I really
feel like you can enrich my mind with your opinions on that kind of
questions I should ask. Don't feel compelled to write anything in
responce, especially if you have nothing relevant to say on the
subject...

I guess Andrew provided some "pithy" comments... his signal to noise ration
hit such a downward trend that I finally killfiled him. You might want to do
the same. Now the only things I see that are connected with him are the
occasional responses like yours.