# Daily Archives: April 27, 2011

## Recursion III, using Java

Here’s a Java example of the classic recursion/tree/web traversal. Note that this uses an array of other nodes, not just Left and Right, so you can make n-link webs as well as proper trees using this example.

The method interMed() is used to avoid having to make the data structures static- there is much I have yet to learn about Java! But I can manage this, and that feels pretty good!

```/* recurse.java```

``` Recursive tree/web traversal, in Java. No explicit pointers, so I state that the array of pointers to nodes is an array of nodes, and treat it as such. Is it really pointers if I believe it is but can't see them? Its like String Theory... Original 11:58am 4/21 Bill4 */ import java.util.ArrayList; public class recurse { public class node { String name; ArrayList kids; }; public class leveledName { String name; int level; }; ArrayList nLs = new ArrayList (); public void recur ( node n, int level ) { // System.out.println( "recur " + n + " level " + level ); leveledName lN = new leveledName(); lN.name = n.name; lN.level= level; nLs.add( lN ); for ( int i = 0; i < n.kids.size(); i++ ) { // better way to do this? recur( n.kids.get(i), level + 1 ); } // for int i... } // recur function public void interMed() { node Q = new node(); Q.name = "Q"; Q.kids = new ArrayList (); // System.out.println( Q ); node S = new node(); S.name = "S"; S.kids = new ArrayList (); // System.out.println( S ); node T = new node(); T.name = "T"; T.kids = new ArrayList (); // System.out.println( T ); node N = new node(); N.name = "N"; N.kids = new ArrayList (); N.kids.add(Q); // System.out.println( N ); node P = new node(); P.name = "P"; P.kids = new ArrayList (); P.kids.add(S); P.kids.add(T); // System.out.println( P ); node M = new node(); M.name="M"; M.kids = new ArrayList (); M.kids.add(N); M.kids.add(P); // System.out.println( M ); recur( M, 0 ); int maxLevel = 0; for ( int i = 0; i maxLevel) { maxLevel = ((nLs.get(i)).level ); } // if ... } // for ... for (int j = maxLevel; j > -1; j-- ) { // System.out.println( "j " + j ); for ( int i = 0; i < nLs.size(); i++ ) { // System.out.println( "j " + j + " i " + i ); if ( j == (nLs.get(i)).level ) { System.out.printf( "%s %d \n", (nLs.get(i)).name, (nLs.get(i)).level ); } } // for i... } // for j... } // fn interMed public static void main ( String args[] ) { recurse r = new recurse(); r.interMed(); } // main ```

```} // class recurse ```