Computer Science · Grade 12

Active learning ideas

Tree Traversal Algorithms

Tree traversal algorithms can feel abstract to students because the path through nodes isn't visible without deliberate practice. Active learning works well here because movement and physical or visual representation help students internalize the order of visits, turning abstract steps into concrete actions they can discuss and revise in real time.

• Ontario Curriculum Expectations
• CS.DSAA.8
• CS.P.8

• 25–50 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Peer Teaching
• 30 min · Pairs

Pairs: Tree Tracing Challenge

Partners draw a binary tree on paper and trace in-order, pre-order, and post-order paths with colored markers, predicting outputs before verifying. Switch roles for a second tree. Discuss differences in results.

Compare the output of in-order, pre-order, and post-order traversals for a given binary tree.

Facilitation Tip

During the Tree Tracing Challenge, circulate and listen for pairs correcting each other's paths, stepping in only if misconceptions persist beyond one repetition.

What to look for

Provide students with a small, labeled binary tree. Ask them to write down the sequence of nodes visited for each of the three traversal types (in-order, pre-order, post-order). Check for accuracy in node order.

• Understand
• Apply
• Analyze
• Create
• Self-Management
• Relationship Skills

Activity 02

• Peer Teaching
• 45 min · Small Groups

Small Groups: Physical Node Simulation

Use index cards as nodes labeled with values; groups arrange into a tree and walk traversals by passing a token node-by-node. Record sequences on shared charts. Compare with code outputs.

Explain the practical applications of each tree traversal method.

Facilitation Tip

For Physical Node Simulation, assign roles clearly so students rotate responsibilities and stay engaged during each traversal.

What to look for

Pose the question: 'When would you choose pre-order traversal over in-order traversal, and why?' Facilitate a class discussion where students justify their choices with specific application examples, such as copying a tree versus sorting its elements.

• Understand
• Apply
• Analyze
• Create
• Self-Management
• Relationship Skills

Activity 03

• Peer Teaching
• 25 min · Whole Class

Whole Class: Live Projection Trace

Project a complex tree; class votes or calls out next node in sequence for each traversal type. Students note on personal worksheets. Reveal full outputs for analysis.

Design an algorithm to find the minimum value in a binary search tree.

Facilitation Tip

In Live Projection Trace, pause after each step to ask students to predict the next node, keeping them actively involved.

What to look for

On an index card, ask students to write the definition of post-order traversal in their own words and provide one scenario where this traversal method would be particularly useful, such as evaluating a mathematical expression in postfix notation.

• Understand
• Apply
• Analyze
• Create
• Self-Management
• Relationship Skills

Activity 04

• Peer Teaching
• 50 min · Individual

Individual: Code Implementation

Students code recursive functions for all three traversals in Python or Java, test on provided trees, and extend to find BST minimum. Submit outputs with explanations.

Compare the output of in-order, pre-order, and post-order traversals for a given binary tree.

Facilitation Tip

When students code implementations, provide starter code with print statements so they focus on logic rather than syntax errors.

What to look for

Provide students with a small, labeled binary tree. Ask them to write down the sequence of nodes visited for each of the three traversal types (in-order, pre-order, post-order). Check for accuracy in node order.

• Understand
• Apply
• Analyze
• Create
• Self-Management
• Relationship Skills

A few notes on teaching this unit

Teaching traversal algorithms works best when teachers model the physical act of moving through nodes first, then transition students to abstract representations. Avoid rushing to code; let students articulate the order of visits in their own words before formalizing it. Research shows that students benefit from comparing traversals side-by-side on the same tree, so display all three sequences simultaneously to highlight differences.

Successful learning looks like students confidently explaining and demonstrating the difference between traversal types, using correct terminology to describe node visits, and choosing the appropriate traversal for given tasks without hesitation. Evidence includes accurate written sequences, clear physical demonstrations, and justifications during discussions.

---

Watch Out for These Misconceptions

• During Tree Tracing Challenge, watch for pairs starting in-order traversals at the root. Redirect them by having them trace left subtree first, then root, then right subtree, using the provided labeled tree to mark each step.

  During Physical Node Simulation, watch for students assuming pre-order and post-order outputs are identical. Have groups physically walk through both traversals on the same tree, then compare their final node visit orders to see the difference in sequence.

• During Live Projection Trace, watch for students generalizing that traversals only work for binary search trees. Pause the trace to highlight the tree’s structure, then ask students to predict outputs for a non-BST binary tree to test their understanding.

  During Physical Node Simulation, watch for students assuming traversals only work for binary search trees. After completing the simulation, provide a general binary tree and ask groups to perform all three traversals, comparing results to confirm the methods apply universally.

---

Methods used in this brief

• Peer Teaching