When do we use preorder, postorder traversal?

[Shanin]

Hello, I have a question about tree traversal.

When do we use inorder, preorder, postorder traversal in search trees?

In actual programming, I do like this:

1. visit root
2. decide to go to left or right

for example:


5
/ \
3 7

input value : 3

visit root : 5 (3<5, go to the left)
visit left : 3 (3=3)


Did I use inorder, preorder or postorder traversal? Neither of them? Futhermore, when is each tree traversal useful?

Thanks in advance. :)

[Ejaz]

Tree traversal provides for sequential processing of each node in what is, by nature, a non-sequential data structure. Such traversals are characterised by the order in which the nodes are visited.

Say we have a tree node structure which contains a value value and references left and right to its two children. Then we can write the following function:

visit(node)
print node.value
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)

This prints the values in the tree in pre-order. In pre-order, each node is visited before any of its children.

Similarly, if the print statement were last, each node would be visited after all of its children, and the values would be printed in post-order. In both cases, values in the left subtree are printed before values in the right subtree.

visit(node)
if node.left != null then visit(node.left)
print node.value
if node.right != null then visit(node.right)

An in-order traversal, as above, visits each node between the nodes in its left subtree and the nodes in its right subtree. This is a particularly common way of traversing a binary search tree, because it gives the values in increasing order.

To see why this is the case, note that if n is a node in a binary search tree, then everything in n's left subtree is less than n, and everything in n's right subtree is greater than or equal to n. Thus, if we visit the left subtree in order, using a recursive call, and then visit n, and then visit the right subtree in order, we have visited the entire subtree rooted at n in order.

If instead we visit the right subtree, then the current node, then the left subtree, this produces the opposite order as in-order traversal, sometimes called a reverse in-order or reverse-order traversal.


................................. 2
.............................. /...\
..............................7.....5
............................./.\.....\
............................2...6.....9
................................/.\.../
...............................5...11.4

In this binary tree,
Preorder traversal yields: 2, 7, 2, 6, 5, 11, 5, 9, 4
Postorder traversal yields: 2, 5, 11, 6, 7, 4, 9, 5, 2
In-order traversal yields: 2, 7, 5, 6, 11, 2, 5, 4, 9

The inorder traversal is of course how we typically write these expressions. The postorder is how, for example, an HP calculator expects its input, and preorder is how many functional programming languages operate (e.g., Lisp, Scheme), and indeed, how functions are written: the function name comes first, then its arguments.