SHSubjectHub

Tree Traversal & Reverse Polish Notation

AQA 75174.3bA-levelWorksheetSubscription
Page 1 of the Tree Traversal & Reverse Polish Notation preview
1 of 3 in the preview
Also online

This worksheet marks itself

Set it as homework or classwork and every answer is marked as pupils go, with feedback on what they got wrong. The scores go straight into your mark book, so you can see who needs help before the next lesson.

  • 12 questions
  • 46 marks
  • about 55 minutes
  • marked instantly

Question types: short answer, multi-part, multiple choice, matching, true or false.

Try it with a class, freeHow it works

About this resource

AQA A-level Computer Science (7517) Paper 1, 4.3.2 Tree-traversal and 4.3.3 Reverse Polish — be able to trace the pre-order, post-order and in-order tree-traversal algorithms and describe their uses (pre-order for copying a tree; in-order for outputting a binary search tree's contents in ascendin…

Lesson outline

  1. Do Now — Retrieval from 4.2.5 Trees
  2. Hinge Check — What Does 'Traversal' Actually Mean?
  3. I-Do: Three Traversal Orders — Where Does the Root Get Visited?
  4. We-Do: Our Worked Tree for All Three Traversals
  5. Hinge Check — Predict Before We Trace
  6. I-Do: Tracing Pre-order (root, left, right)
  7. I-Do: Tracing In-order (left, root, right)
  8. I-Do: Tracing Post-order (left, right, root)
  9. We-Do — Trace All Three Orders on a New Tree
  10. Hinge Check — In-order Always Gives Sorted Output?
  11. I-Do: What Is Each Traversal Order Used For?
  12. We-Do — Matching: Traversal Order to Its Use
Unit bundlePaper 1
Part of: Paper 1: the whole unitEvery resource in the unit in one zip.

More from 4.3 Fundamentals of algorithms