Tree Traversal

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:

  1. visit all of the nodes in the subtree topped by $n$'s left child first,
  2. then we visit $n$ itself, and
  3. finish by visiting all of the nodes in the subtree topped by $n$'s right child.

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:

  1. one first visits all of the nodes in the subtree topped by $n$'s left child first,
  2. then one visits all of the nodes in the subtree topped by $n$'s right child, and
  3. finally, one visits $n$ itself

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:

  1. one visits $n$ itself
  2. then one visits all of the nodes in the subtree topped by $n$'s left child first, and
  3. finally, one visits all of the nodes in the subtree topped by $n$'s right child.

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: