By: Nicholas Duchon.

The Wiki has a nice article:

http://en.wikipedia.org/wiki/Tree_traversal

Here's a fairly simple example:

X in-order:

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75

X pre-order:

40 20 10 5 15 30 25 35 60 50 45 55 70 65 75

X post-order:

5 15 10 25 35 30 20 45 55 50 65 75 70 60 40

X level-order:

40 20 60 10 30 50 70 5 15 25 35 45 55 65 75

Here are the basic algorithms:

In order, recursive

visit left node

visit this node

visit right node

Pre order, recursive

visit this node

visit child nodes

Post order - recursive

visit child nodes

visit this node

Level order = breadth first - best using a queue (FIFO):

enqueue root

while queue not empty

node = dequeue

visit node

enqueue child nodes

end while

Depth first - best using a stack (LIFO):

push root

while stack not empty

node = pop

push child nodes

visit node

end while

Level-order implements a breadth-first ordering of a tree or a graph (if you add code to make sure nodes are only visited once).

Note also that pre, post and level order make sense in any tree, but in-order only makes sense in a BINARY tree.

ND.