Tree Traversals - top of Musings page

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.