Computer Science · Grade 12

Active learning ideas

Binary Search Trees: Structure

Students learn binary search trees best when they physically build and manipulate the structure rather than just observe it. Active learning helps them internalize how comparisons create order and how each insertion or deletion affects the tree’s balance and search paths. Moving beyond abstract discussion makes the O(log n) complexity feel intuitive through direct experience.

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

• 20–35 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Gallery Walk
• 25 min · Pairs

Pair Activity: Card-Based Tree Construction

Provide pairs with numbered cards and blank tree diagrams. Partners take turns drawing a card, comparing its value to the current root and subtrees to insert it correctly, then verify the structure against rules. Switch roles after five insertions and discuss shape changes.

How does the shape of a tree affect the efficiency of data retrieval?

Facilitation Tip

For the card-based tree construction activity, circulate and ask pairs to verbally state each comparison aloud before placing a card to reinforce decision-making.

What to look for

Present students with a sequence of numbers (e.g., 50, 30, 70, 20, 40, 60, 80). Ask them to draw the resulting binary search tree. Then, ask them to trace the path to find the value 40 and state its time complexity.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

Activity 02

• Gallery Walk
• 35 min · Small Groups

Small Groups: Insertion Race Challenge

Give groups a list of 15 numbers and large whiteboards. Groups compete to build the tallest valid BST by inserting sequentially, checking peers' trees for errors mid-process. Debrief on why certain sequences produce skewed shapes.

Explain the rules for inserting and deleting nodes in a binary search tree.

Facilitation Tip

During the insertion race challenge, set a strict timer for each round and ask groups to present their tree’s final shape to the class, encouraging comparisons of different insertion sequences.

What to look for

Pose the question: 'Imagine you are building a BST for a dictionary. What would happen to the tree's shape and search efficiency if you inserted words in alphabetical order? How does this compare to inserting them randomly?' Facilitate a discussion on balance and performance.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

Activity 03

• Gallery Walk
• 30 min · Whole Class

Whole Class: Interactive Deletion Simulation

Project a large BST on the board. Class votes on deletion targets, teacher demonstrates steps while students note changes on handouts. Follow with pairs replicating two deletions independently.

Construct a binary search tree from a given set of data.

Facilitation Tip

In the interactive deletion simulation, pause after each case vote to have students sketch the tree before and after the deletion on mini-whiteboards for immediate feedback.

What to look for

Give students a small BST diagram. Ask them to write down the steps to delete the node with the value 30, assuming it has two children. They should explain the replacement strategy used.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

Activity 04

• Gallery Walk
• 20 min · Individual

Individual: Code Tracer Worksheet

Students trace code snippets for BST insertion on pre-drawn trees, marking paths and noting violations. Then code a simple inserter function, test with provided data, and measure search times on balanced versus skewed inputs.

How does the shape of a tree affect the efficiency of data retrieval?

Facilitation Tip

Have students complete the code tracer worksheet step-by-step with a partner, using colored pencils to mark each node’s path and changes during insertion or deletion.

What to look for

Present students with a sequence of numbers (e.g., 50, 30, 70, 20, 40, 60, 80). Ask them to draw the resulting binary search tree. Then, ask them to trace the path to find the value 40 and state its time complexity.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

A few notes on teaching this unit

Experienced teachers approach BSTs by first grounding the concept in physical models before moving to code, because the abstract rules become concrete when students hold the nodes in their hands. Avoid rushing to the algorithmic steps without letting students first experience the consequences of poor insertion order, as this delays the need for balancing techniques. Research shows that students retain the order property better when they physically rearrange nodes and measure path lengths themselves.

By the end of these activities, students will construct balanced and unbalanced BSTs correctly, explain insertion logic using comparisons, execute deletions in all three cases, and connect tree shape to search efficiency. They will also justify their steps with evidence from the models they create.

---

Watch Out for These Misconceptions

• During the card-based tree construction activity, watch for groups assuming the tree will always stay balanced after insertions.

  After building the tree with a sorted sequence, ask groups to measure the height and trace the path to find a leaf node, then have them compare it to a tree built from random numbers. Use their observations to connect tree shape to performance.

• During the interactive deletion simulation, watch for students believing deletion simply removes the node without restructuring the tree.

  After voting on deletion cases, pause the simulation and ask students to redraw the tree before and after deletion on mini-whiteboards. Require them to label the successor and trace the path to verify the BST property is maintained.

• During the insertion race challenge, watch for students assuming search steps are identical regardless of tree shape.

  After each round, time how long it takes students to find a specific value in their trees. Ask them to compare their times to the height of the tree and predict the Big O complexity based on their observations.

---

Methods used in this brief

• Gallery Walk