Exam-style question
Try this first
An expression tree has / as its root. Its left child is - and its right child is +. The - node has leaves x and y. The + node has leaves z and 2. Trace a post-order traversal and write the resulting postfix expression. Explain why post-order is suitable for producing a postfix expression from an expression tree, and give one other specified use of post-order traversal.
Model answer
What a good answer should say
- The post-order traversal is x, y, -, z, 2, +, /.
- The postfix expression is x y - z 2 + /.
- Post-order places each operator after the values or subexpressions on which it operates, so it produces a postfix expression from the expression tree.
- Another specified use is emptying a tree.
Explanation
Why this works
The left subtree is visited first, producing x y -. The right subtree is then visited, producing z 2 +.
Finally, the root operator / is visited. This gives x y - z 2 + /, with each operator appearing after its corresponding subexpressions.
Common mistake
No common mistake is linked to this question yet.