# Traditional Ways of Tree Traversal

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
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())
// 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();
}
}
}
}
``````