Subj : Recursion in Java: Question for those who understand recursion well.
To   : comp.programming
From : success_ny
Date : Fri Aug 26 2005 05:10 pm

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.

.