Computer Science · 12th Grade

Active learning ideas

Binary Search Trees (BSTs)

Binary Search Trees make abstract tree theory concrete by connecting structure to performance. Active learning works here because students need to internalize the BST invariant through physical movement and iterative debugging, not just reading code. When they build or trace trees by hand, the cost of imbalance becomes visible in minutes, not after hours of runtime errors.

• Common Core State Standards
• CSTA: 3B-AP-12
• CSTA: 3B-AP-14

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

Activity 01

• Simulation Game
• 30 min · Whole Class

Simulation Game: Build a Human BST

Each student receives a number card. As the teacher calls out values for insertion, each student finds their correct position relative to the existing class-tree, physically standing left or right of existing students based on the BST invariant. When all students are placed, the class performs an in-order traversal by calling out numbers in sequence, confirming sorted output. The teacher then inserts in sorted order to show the tree degenerating into a line.

Explain how a balanced tree differs from an unbalanced one in terms of search speed.

Facilitation Tip

During Build a Human BST, stand at the front and deliberately insert in sorted order to create a linked list, then ask students to time a search across the chain versus a balanced tree they just built.

What to look for

Provide students with a list of 10 numbers. Ask them to draw the BST that results from inserting these numbers in the given order. Then, ask them to calculate the height of the resulting tree and state its time complexity for searching.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 02

• Problem-Based Learning
• 60 min · Pairs

Collaborative Lab: Implement and Stress Test

Pairs implement a BST with insert, search, and delete methods, then test with three different insertion orderings: random, sorted ascending, and sorted descending. After each, they call a function that computes the tree's height and record results for all three cases with the same set of values. Pairs graph their height results and write a brief analysis of why the same values produce such different structures.

Analyze the worst-case scenarios for BST operations and how they can be mitigated.

Facilitation Tip

In Collaborative Lab, pair each coding group with a peer group whose tree they will test, making performance trade-offs visible through shared data.

What to look for

Pose the question: 'Imagine you are designing a system to store and retrieve customer order IDs. Under what circumstances would a BST be the optimal data structure, and what potential pitfalls would you need to consider regarding data input?' Facilitate a class discussion on their reasoning.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Activity 03

• Think-Pair-Share
• 25 min · Pairs

Think-Pair-Share: When Would a BST Fail?

Present a scenario: a database that stores user IDs assigned sequentially (1, 2, 3...) using a BST for lookup. Students individually predict the tree shape and search performance, then pair up to design a simple test that would confirm their prediction. The class compiles the worst-case scenarios they identified and discusses practical implications for database design.

Design a system where a BST would be the optimal choice for data storage and retrieval.

Facilitation Tip

For Gallery Walk, ask each group to prepare a 60-second explanation of how their traced operation preserves the BST invariant, then rotate so every student sees three different correctness criteria.

What to look for

Present students with two code snippets: one implementing a BST insertion and another implementing a simple linked list insertion. Ask them to identify which snippet represents the BST and explain why the BST's insertion logic, when applied to sorted data, leads to a degenerate structure.

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

Activity 04

• Gallery Walk
• 40 min · Pairs

Gallery Walk: BST Operations Traced

Post 5 stations showing BSTs with a pending operation: search for a value, insert a new value, delete a leaf, delete a node with one child, and delete a node with two children. Student pairs trace each operation step by step on the diagram, circling the decision point at each node. The two-child deletion case is discussed as a class after the walk, with pairs sharing their approaches.

Explain how a balanced tree differs from an unbalanced one in terms of search speed.

Facilitation Tip

During Think-Pair-Share, assign one student to argue for BST superiority and another to find the worst-case input order, forcing them to confront failure modes immediately.

What to look for

Provide students with a list of 10 numbers. Ask them to draw the BST that results from inserting these numbers in the given order. Then, ask them to calculate the height of the resulting tree and state its time complexity for searching.

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

A few notes on teaching this unit

Teach BSTs by making the invariant tangible first, then layering code on top. Avoid introducing balancing algorithms too early; let students feel the pain of degenerate trees before they learn rotations. Research shows that students who physically build trees retain the performance implications of structure better than those who only code abstract nodes. Use deletion as the culminating challenge—it forces students to confront the recursive nature of tree operations in a way that insertion rarely reveals.

You'll see students accurately trace insertions and deletions, predict tree heights from input order, and justify performance claims with evidence from their own structures. Struggling learners will move from copying code to explaining why a specific tree shape leads to O(n) time, while advanced students will connect input order to rebalancing strategies.

---

Watch Out for These Misconceptions

• During Build a Human BST, watch for students who assume the tree is balanced regardless of insertion order.

  After the activity, have each group present the height of their tree and ask the class to identify which insertion sequence caused the imbalance. Display the sorted sequence and the linked-list structure side by side to make the connection explicit.

• During Collaborative Lab, watch for students who treat deletion as a simple removal of the target node.

  Require each group to trace their deletion on a whiteboard using the three-case algorithm with colored markers: one color for the node to delete, another for the successor, and a third for the replacement value, forcing them to follow the full procedure.

• During Gallery Walk, watch for students who equate BST performance with sorted array performance.

  Ask each group to annotate their traced operations with the time complexity for that specific step, then compare their BST's insertion time to what would happen if the same data were stored in a sorted array, using actual timings from the lab.

---

Methods used in this brief

• Simulation Game
• Problem-Based Learning
• Think-Pair-Share
• Gallery Walk