# Depth and breadth first tree traversal

A friend of mine mentioned depth and breadth first tree traversal today and since I didn’t have a post on this already I thought this would be a good opportunity to do one and post my take on it. This focuses more on depth and breadth first tree traversal as opposed to graph search and whereas the algorithm is identical to how you’d expect an iterative dfs/bfs traversal to be there are a couple of small differences in the way I’ve done it here which may be serve as useful tips.

### Node

The first thing we need is the classic Node class which has an identity and children.

[java]
package name.dhruba.kb.algos.dfsbfs;

class Node {

final String name;
final Node[] children;

Node(String name) {
this.name = name;
this.children = new Node[0];
}

Node(String name, Node[] children) {
this.name = name;
this.children = children;
}

boolean hasChildren() {
return children != null && children.length > 0;
}

@Override
public String toString() {
return name;
}

}
[/java]

### Depth and breadth first traversal

Now here is the depth and breadth first traversal algorithm. Observations on the code follow underneath.

[java]
package name.dhruba.kb.algos.dfsbfs;

import java.util.ArrayDeque;
import java.util.Deque;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

class DfsBfsTraverser {

static final Logger logger = LoggerFactory.getLogger(DfsBfsTraverser.class);

enum TraversalType {
}

interface NodeProcessor {
void process(Node node);
}

static void traverse(Node root, TraversalType traversalType,
NodeProcessor processor) {

if (root == null) {
return;
}

if (!root.hasChildren()) {
processor.process(root);
return;
}

Deque<Node> deck = new ArrayDeque<Node>();

while (!deck.isEmpty()) {

Node current = deck.removeFirst();

if (current.hasChildren()) {
for (Node child : current.children) {
}
}

try {
processor.process(current);
} catch (Exception e) {
logger.error("error processing node", e);
}

}

}

static void addToDeck(Deque<Node> deck, TraversalType traversalType,
Node node) {
if (traversalType == TraversalType.DEPTH_FIRST) {
} else {
}
}

}[/java]

### Observations

• Note that the iterative algorithm implementation for depth and breadth first traversal are so similar that there’s no need to do a separate one for each. This class has quite easily been modified very subtly to accommodate both.
• Note the use of ArrayDeque as a highly efficient stack confined deque. This allows us to add both to the front and back depending on the traversal type. It is also important to note that this class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue as mentioned in its javadocs.
• Note the initial elimination cases where we can get away with doing the bare minimum.
• And finally note the use of a callback which allows the caller to do as they wish. This may seem like a small measure now but in the next post on this subject I’ll go into how to use the callback to allow the caller to dictate how far and in which direction they want to traverse based on the return value of the callback as well as how to allow the caller to terminate the traversal when they’ve found what they’re looking for. Such functionality can be critrical to good performance.

### Testing

Take the following tree as an example.

```       a
/
b      c
/      /
e     f g    h
```

DFS returns: [a, c, h, g, b, f, e]
BFS returns: [a, b, c, e, f, g, h]

Note that DFS progresses from right to left due to the order in which children are added and removed from the deque.