Traditional Ways of Tree Traversal

This page contains examples of some “standard” traversal algorithms (ones that
can be found in most textbooks). All examples perform pre-order tree traversal
on a general rooted tree. “Algorithms, Data Structures and Problem Solving with
C++” by Mark Allen Weiss (Addison-Wesley, 1995) gives the following definition
of the general rooted tree:

• One node is distinguished as a root.

• Every node c, except the root, is connected by an edge from exactly one
  other node p. p is the parent and c is one of p‘s
  children.

• There is a unique path from the root to each node. The number of edges that must
  follow is the path length (sometimes it is called “depth”).

Binary trees and their variations (AVL, red-black and so forth) are not
considered here.

Each example performs full traversal of a DOM
tree and prints name and value of each node. An XML parser, for example Apache’s
Xerces, is needed in order to run the code.

Example 1. Traversal using recursion

Recursive traversal is the best known and most frequently used. Recursive
algorithm uses method call stack in order to keep the state of the traversal for
every level of a tree. There is a common misconception that recursive algorithms
are slow because of the call stack copying overhead. I have not found it to be
the case in Java, at least it is not the case for methods with small number of
local variables.

import org.w3c.dom.*;

public class RecursiveTraversal implements ITraversal {

  /**
   * Performs full tree traversal using recursion.
   */
  public void traverse( Node parentNode ) {
    // traverse all nodes that belong to the parent
    for(Node node=parentNode.getFirstChild(); node!=null; node=node.getNextSibling()
    ) {
      // print node information
      System.out.println( node.getNodeName()+"="+node.getNodeValue());
      // traverse children
      traverse(node);
    }
  }
}

Example 2. Traversal using stack

A stack object is used to store tree level’s state thus eliminating the need for
recursion.

Note that in reality you don’t want to use java.util.Stack because
its methods are synchronized. It also inherits from Vector and its
methods are synchronized as well. So some sort of custom stack class (for
example, based on java.util.ArrayList) should be used instead.

import org.w3c.dom.*;
import java.util.*;

public class StackTraversal implements ITraversal {

  /**
   * Performs full tree traversal using stack.
   */
  public void traverse( Node rootNode ) {

    Stack stack = new Stack();
    // ignore root -- root acts as a container
    Node node=rootNode.getFirstChild();

    while (node!=null) {
      // print node information
      System.out.println( node.getNodeName()+"="+node.getNodeValue());

      if ( node.hasChildNodes()) {
        // store next sibling in the stack. We return to it after all children are
        processed.
        if (node.getNextSibling()!=null)
          stack.push( node.getNextSibling() );
        node = node.getFirstChild();
      }
      else {
        node = node.getNextSibling();
        if (node==null && !stack.isEmpty())
          // return to the parent's level.
          // note that some levels can be skipped if the parent's node was the last one.
          node=(Node) stack.pop();
      }
    }
  }
}

Example 3. Traversal using child-parent link

It is possible to avoid using stack for treelike structures that provide support
for child-parent link. Link from child to parent can be used to return back to
the parent level once the child level is processed. This link effectively
simulates stack, so there is no need for a separate stack object. Most of the
tree types (including DOM) do support child-parent link. This is probably the
most elegant way of traversing a tree — no recursion or stack is involved.

import org.w3c.dom.*;

public class LinkTraversal implements ITraversal {

  /**
   * Performs full tree traversal using child-parent link.
   */
  public void traverse( Node rootNode ) {

    // ignore root -- root acts as a container
    Node node=rootNode.getFirstChild();

    while (node!=null) {
      // print node information
      System.out.println( node.getNodeName()+"="+node.getNodeValue());

      if ( node.hasChildNodes()) {
        node = node.getFirstChild();
      }
      else {    // leaf
        // find the parent level
        while (node.getNextSibling()==null && node != rootNode)
            // use child-parent link to get to the parent level
            node=node.getParentNode();

        node = node.getNextSibling();
      }
    }
  }
}