Tree-traversal study guide

A reliable tracing method

Start at the root and write down the required order for the traversal: pre-order is root-left-right, in-order is left-root-right, and post-order is left-right-root. Do not list a node merely because you first reach its position. Instead, apply the rule recursively to each subtree.

For a tree whose root is M, whose left subtree has root F with children B and H, and whose right child is T, trace the left subtree and right subtree according to the same rule:

• Pre-order: visit M, then traverse F before T. The result is M, F, B, H, T.
• In-order: traverse the left side of F, visit F, then its right side; visit M; then visit T. The result is B, F, H, M, T.
• Post-order: complete both subtrees before their parent. The result is B, H, F, T, M.

The important reasoning is not just the final sequence. For example, in post-order, F cannot be output until both B and H have been output, and M cannot be output until both complete subtrees have been processed.

Applying the specified uses

For copying a tree, use pre-order and create or copy the current node before recursively handling its subtrees. This preserves the relationship between a parent and the children that are copied beneath it.

For a binary search tree, use in-order traversal when the required result is the contents in ascending order. The left subtree is output before the root, and the right subtree is output after the root, giving the required ordering for the binary search tree.

For infix to RPN conversion, use post-order on an expression tree. An operator is produced after the expression represented by its left subtree and the expression represented by its right subtree. This places the operator after its operands, which is the postfix arrangement. The same post-order reasoning applies when producing a postfix expression from an expression tree.

For emptying a tree, post-order ensures that a node's subtrees are processed before the node itself. When tracing, check that every child appears before its parent.

Exam application checklist

1. Identify the traversal named in the question.
2. Write its three-part order before starting.
3. Mark the root, then trace the left and right subtrees recursively.
4. Check that every node appears exactly once.
5. If the question asks for a use, connect the order to the stated task rather than giving an unrelated example.
6. If the tree is a binary search tree and in-order is requested, check that the output is ascending.
7. If post-order is used for postfix output, check that operands occur before their operator.

Self-check questions

Can you explain why pre-order is suitable for copying a tree? Can you trace all three orders for a tree with missing children? Can you explain why in-order output is ascending specifically for a binary search tree? Can you identify which traversal places a parent after both children? Finally, given an expression tree, can you justify each symbol's position in the postfix result rather than only writing the final sequence?