How to traverse a level-oriented structure?

I have a linear data structure where every node has a level. The parent node has a level of 1, a node that is child of the parent has a level 2, a node that is child of child has node of 3, another parent node would have a level of 1. e.g. below

<node level=1> //parent node
<node level=2> //child of encountered parent node
<node level=2> //child of encountered parent node
<node level=3> //child of encountered child node
<node level=2> //child of encountered parent node
<node level=1> //parent node
<node level=1> //parent node
<node level=2> //child of encountered parent node
<node level=3> //child of encountered child node
<node level=4> //child of encountered child node
<node level=1> //parent node

Essentially I am trying to build a List. (Open to other suggestions), such that each element in the list is a parent node, each parent node will have list of child nodes, each child node can have list of child nodes etc. Each of the element is a node and all properties are same.

I have tried code by keeping track of the current level but than I am not sure how to properly add a child node, that has child node, that has child node, back to the parent node of the first child node. I feel this might be handled best by recursion but I am have never been able to truly implement recursion in an orderly fashion.

Solution

You don't have to think about all the nesting. You only have to think about where you are (as in, what level was the previous entry in the list of nodes) and where the next entry goes.

In this case, the solution lies in the way the tree is read in. Notice in your list of nodes, which is the tree input source, that right after a parent node, the next node is a child. If the node after some node isn't a child of that node (i.e. if its level isn't one level lower), it is the child of one of the previous node's ancestors.

So:

If the level on line n is equal to one plus the level on line n-1, line n holds a child of line n-1.
Otherwise, go up the tree from the node for line n-1 until you find one with a level one less than the level on line n. That ancestor node is the parent of node on line n.

You also don't have to do it recursively.

currLevel = 0;
currNode = root;
do {
   node = read();
   if (somethingRead()) {
      // If this one is one level below the last one, it goes in as a child and we're done
      if (node.level == currNode.level + 1) {
         currNode.addChild(node);
         currNode = node;
      } else {
         // Otherwise this one has to be at a level above this node's child, so back up
         while (node.level >= currNode.level) {
            currNode = currNode.parent(); // check for root left out here ...
         }
         if (node.level == currNode.level + 1) {
            currNode.addChild(node);
            currNode = node;
         } else {
            // handle illegal condition in list
         }
      }
   }
} while (moreNodesToRead());

Response to Your Solution

Your solution reflects your reluctance to use a fake node as the root of the tree. That's a design choice one can make. Here is my version of it.

I am a little concerned about how you handle incoming data that is fouled up

A node is presented that is more than one level beyond the one before it.
The first node presented isn't at level 1.
A node has a level of 0 or less (no checks for that below)

Also, I suggest you allow currNode to be null when the current node should be the root. Theoretically it could happen in the while loop that backs up the current node but notice that, at that point in the code, you already know the new node has a level above 1 so currNode should never back up beyond the level 1 nodes. It is reasonable to have it generate a NPE if that assumption is wrong.

I suggest these changes:

Node currNode = null;
List<Root> roots = new ArrayList<Root>();

do {
      Node node = generateNode(nodesList.next());
      if (node.getLevel() == 1) { //implies root level node
         roots.add(node);
         currNode = node;
      } else if (currNode == null) {
         // ... handle misformed input ... first node isn't level 1, ignore it
      } else if (node.getLevel() == currNode.getLevel() + 1) {
         currNode.childrenList.addChild(node);
         node.setParent(currNode);
         currNode = node;
      } else {
         Node savedCurrNode = currNode;
         while (node.getLevel() <= currNode.getLevel()) {
             currNode = currNode.getParent();
         }
         if (node.getLevel() == currNode.getLevel() + 1) {
             currNode.childrenList.addChild(node);
             node.setParent(currNode);
             currNode = node;
         } else {
             // ... handle misformed input ... node level > last node level + 1, ignore it
             currNode = savedCurrNode;
         }

} while (hasMoreNodes(nodesList));

Printing

I rearranged it a bit and changed some names and responsibilities (listed in comments). Just to belabor a point from above, if the root was just a node you wouldn't need the 'printRoots()' method at all. Just call 'printChildren()' on the fake root node with level set to 0. But it would print one extra line at the top.

(It always makes it easier to read if you indent the output.)

Warning: Not tested.

/** Print all the root nodes, each with any children it may have */
private void printRoots(List<Node> roots) {

    for (int j = 0; j < roots.size(); j++) {
        Node node = roots.get(j);
        printContents(node, 1);
    }

}

/** Print one node and any children it might have */
private void printContents(Node node, int level) {

    for (int i=1 ; i < level ; ++i) {
        print("    ");
    }
    print(node.toString());
    println();

    printChildren(node, level+1);

}

/** Print each child of the supplied node. Notice how this is just like getting the
 * list of children and calling 'printRoots()'
 *//
private void printChildren(Node node, int level) {

    for (int i = 0; i < node.getChildrenList().size(); i++) {
        Node childNode = node.getChildrenList().get(i);
        printContents(childNode, level);
    }

}