Exam-style question
Try this first
Use the following tree to trace all three traversal algorithms. The root is K. K has left child D and right child S. D has left child B and right child G. S has left child N and right child W. State the pre-order, in-order and post-order sequences. Also state one specified use for each traversal.
Model answer
What a good answer should say
- Pre-order: K, D, B, G, S, N, W.
- In-order: B, D, G, K, N, S, W.
- Post-order: B, G, D, N, W, S, K.
- A specified use of pre-order is copying a tree.
Explanation
Why this works
Pre-order processes the current node before its subtrees, so K is first, followed by the complete left subtree and then the complete right subtree. In-order processes the left subtree, then the current node, then the right subtree.
Post-order processes both subtrees before the current node, so K is last. The uses match the specified applications of each traversal.
Common mistake
No common mistake is linked to this question yet.