Subj : Re: Recursion in Java: Question for those who understand recursion well.
To   : comp.programming
From : Rob Thorpe
Date : Sun Aug 28 2005 04:51 am

success_ny@yahoo.com wrote:
> 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);

Is this cast really necessary?

>         // 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?

As CBFalconer said, show the smallest compilable program you can.  From
reading the above I can't see any obvious mistakes, so long as each
node contains a list and all the functions work as they should.  The
tree should flatten.

Try going though it in a debugger, or printing out the nodes as they're
processed.

.