Computer Science · Grade 11

Active learning ideas

Introduction to Trees and Binary Search Trees

Active learning works well for binary search trees because students need to physically manipulate and visualize the hierarchical structure to understand how ordering affects performance. Moving from abstract definitions to hands-on building and traversing makes the relationship between balance and efficiency concrete and memorable.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

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

Activity 01

• Concept Mapping
• 35 min · Small Groups

Card Sort: Build a BST

Provide decks of numbered cards to small groups. Students insert cards one by one into a physical tree on paper or floor, drawing branches and noting comparisons. Groups then search for target values and time their searches. Debrief on tree shapes formed.

Explain how the structure of a binary search tree enables efficient searching.

Facilitation Tip

During the Card Sort: Build a BST, circulate to ask students to predict the search path for a value before they trace it, reinforcing the relationship between node values and traversal order.

What to look for

Present students with a small, pre-built binary search tree diagram. Ask them to trace the path to find a specific value, writing down each node visited. Then, ask them to determine the time complexity of that search operation.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 02

• Concept Mapping
• 30 min · Pairs

Insertion Simulation: Balance Challenge

Give pairs sorted and random number lists. They build two trees: one from sorted data, one shuffled. Perform multiple searches on each and compare times. Discuss why one skews and rotate nodes to balance it.

Analyze the worst-case scenarios for searching and insertion in a binary search tree.

Facilitation Tip

In the Insertion Simulation: Balance Challenge, have groups time their searches after each insertion to quantify how balance affects performance, making the data meaningful.

What to look for

Provide students with a list of numbers to insert into an initially empty binary search tree. Ask them to draw the resulting tree and then write one sentence explaining why the tree might become unbalanced with certain insertion orders.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 03

• Concept Mapping
• 25 min · Whole Class

Whole Class: Tree Traversal Race

Project a large tree on the board. Assign roles: callers name values, runners trace paths with yarn or pointers. Time in-order, pre-order traversals. Switch roles and vote on fastest method for sorted output.

Design a strategy to balance a binary search tree to maintain optimal performance.

Facilitation Tip

For the Whole Class: Tree Traversal Race, assign roles to students to ensure everyone participates in tracing paths, which prevents passive observation.

What to look for

Facilitate a class discussion using the prompt: 'Imagine you are designing a system to store and quickly search through millions of customer records. How would a binary search tree help, and what potential problems might you encounter with performance?'

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 04

• Concept Mapping
• 40 min · Individual

Individual: Code a Simple BST

Students code insert and search functions in pseudocode or Python starter files. Test with provided datasets, logging heights and search depths. Share one unbalanced case and fix via manual balancing.

Explain how the structure of a binary search tree enables efficient searching.

Facilitation Tip

When students Code a Simple BST, require them to include print statements that show the tree structure after each operation, so they can debug and reflect on their work.

What to look for

Present students with a small, pre-built binary search tree diagram. Ask them to trace the path to find a specific value, writing down each node visited. Then, ask them to determine the time complexity of that search operation.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

A few notes on teaching this unit

Research shows that students grasp binary search trees best when they start with tangible examples before abstracting to code. Avoid rushing to formal definitions; instead, let students discover the ordering property through guided exploration. Emphasize the difference between binary trees (no ordering) and BSTs (ordered) early to prevent later confusion. Use analogies like a dictionary or phone book to ground the concept in real-world examples.

Students will demonstrate understanding by correctly building, traversing, and analyzing binary search trees, explaining how node placement impacts search speed and identifying when trees become unbalanced. They will connect these observations to the importance of maintaining balance for efficient operations.

---

Watch Out for These Misconceptions

• During Card Sort: Build a BST, watch for students who assume a tree is balanced simply because it is a binary tree.

  Ask them to measure the height of their tree and compare it to the number of nodes. Then have them rebuild the tree with the same values in a different order to observe how balance changes.

• During Insertion Simulation: Balance Challenge, watch for students who believe insertion order does not affect the tree's structure.

  Have them insert values in ascending and descending order, then time searches in both trees. Ask them to explain why one tree is faster than the other.

• During Card Sort: Build a BST, watch for students who confuse binary trees with binary search trees.

  Provide a set of values and ask them to build a binary tree first, then convert it to a BST by rearranging nodes. Discuss why the BST allows for efficient searches while the binary tree does not.

---

Methods used in this brief

• Concept Mapping