Unlike linked lists, one-dimensional arrays, and other linear data structures, which are naturally traversed in a linear fashion from one end to the other, tree traversal is a bit more complicated.
In the case of a binary search tree, where all nodes in the subtree topped by the left child of a given node have keys less than the given node's key and all nodes in the subtree topped by the right child of the same node have keys greater than that node, it might be desirable to traverse the tree in a manner where nodes are visited "in order" from the node with the least key to the node with the greatest key.
As an example, consider the tree below:
Wanting to see the elements visited in order (i.e., $A,B,C,D,E,F,G,H,I$), for any subtree's top node $n$ (and starting with the root node), we naturally:
This is known as an in-order traversal of the tree.
Two other tree traversal methods bear mentioning here. Both are recursively defined, like the in-order traversal, in that for any subtree's top node $n$ (again starting with the root node) we visit nodes related to a given subtree's top node in well defined ways:
In a post-order traversal:
In the tree above, this would visit nodes in the following order: $A,C,E,D,B,H,I,G,F$
In a pre-order traversal:
In the tree above, this would visit nodes in the following order: $F,B,A,D,C,E,G,I,H$
Interestingly, there is a strong connection between the tree-traversals described above and the various ways in which we can write mathematical expressions.
For a given mathematical expression, if one constructs a tree where the last operator applied corresponds to the root node, and sub-expressions combined by an operator correspond to subtrees topped by children nodes of some parent (operator) node, then:
As an example, consider the tree for the expression
Both the post-order traversal and post-fix version of the expression is given by
5 z + 8 - / 4 2 ^ *
(Both here and below, the "-" is the unary minus operator, not the subtraction operator)
The pre-order traversal is given by
* / + 5 z - 8 ^ 4 2
and the prefix form of the expression is
( * ( / ( + 5 z ) ( - 8 ) ) ( ^ 4 2 ) )
The in-order traversal is given by
5 + z / - 8 * 4 ^ 2
and the infix form of the expression is
( ( 5 + z ) / ( - 8 ) ) ( 4 ^ 2 )