traversal

data Processing nodes in a graph one at a time, usually

in some specified order. Traversal of a tree is recursively

defined to mean visiting the root node and traversing its

children. Visiting a node usually involves transforming it in

some way or collecting data from it.

In "pre-order traversal", a node is visited _before_ its

children. In "post-order" traversal, a node is visited

_after_ its children. The more rarely used "in-order"

traversal is generally applicable only to binary trees, and is

where you visit first a node's left child, then the node

itself, and then its right child.

For the binary tree:

T

/

I S

/

D E

A pre-order traversal visits the nodes in the order T I D E S.

A post-order traversal visits them in the order D E I S T. An

in-order traversal visits them in the order D I E T S.

(2001-10-01)