early 14c., "pass across, over, or through," from Old French traverser "to cross, thwart" (11c.), from Vulgar Latin *traversare, from Latin transversare "to cross, throw across," from Latin transversus "turn across" (see transverse). The noun meaning "act of passing through a gate, crossing a bridge, etc." is recorded from mid-14c.; meaning "a passage by which one may traverse" is recorded from 1670s. Military foritifcation sense of "barrier, barricade" is recorded from 1590s. Related: Traversed; traversing.
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.