Tree-traversal revision notes

Core idea

A tree-traversal algorithm systematically visits the nodes of a tree. The three required traversal orders are pre-order, in-order and post-order. For each node, consider the node itself, its left subtree and its right subtree.

Traversal orders

Pre-order

Pre-order visits:

1. the current node;
2. the left subtree;
3. the right subtree.

The pattern is root, left, right. A recursive description is:

text preOrder(node) if node is not empty visit node preOrder(node.left) preOrder(node.right)

One specified use of pre-order traversal is copying a tree. Visiting a node before its subtrees allows the corresponding node to be created before its children are copied.

In-order

In-order visits:

1. the left subtree;
2. the current node;
3. the right subtree.

The pattern is left, root, right.

text inOrder(node) if node is not empty inOrder(node.left) visit node inOrder(node.right)

In a binary search tree, in-order traversal outputs the contents in ascending order. For example, for a tree with root 8, left child 3, right child 10, and further nodes 1, 6 and 14, the in-order output is 1, 3, 6, 8, 10, 14.

Post-order

Post-order visits:

1. the left subtree;
2. the right subtree;
3. the current node.

The pattern is left, right, root.

text postOrder(node) if node is not empty postOrder(node.left) postOrder(node.right) visit node

Specified uses of post-order traversal include converting infix expressions to RPN (Reverse Polish Notation), producing a postfix expression from an expression tree, and emptying a tree. A node is processed after its descendants, so its subtrees can be processed before the node itself.

Worked comparison

For a tree with root A, left child B, right child C, and B having children D and E:

• Pre-order: A, B, D, E, C
• In-order: D, B, E, A, C
• Post-order: D, E, B, C, A

Common errors

• Visiting the root first in every traversal. This is only correct for pre-order.
• Swapping the left and right subtree positions when tracing.
• Assuming in-order always produces ascending output. This property applies to a binary search tree.
• Confusing postfix output with infix output when using post-order for an expression tree.
• Processing a parent before its children when the required order is post-order.