Computer Science · 11th Grade

Active learning ideas

Trees: Binary Search Trees

Active learning works for this topic because BSTs are spatial structures that students must visualize and manipulate before they can internalize the ordering rules. Kinesthetic and collaborative activities let students encounter the consequences of insertion order and imbalance in real time, making abstract performance trade-offs concrete.

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

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

Activity 01

• Peer Teaching
• 25 min · Whole Class

Kinesthetic: Human BST Construction

Each student receives a number card. The class inserts numbers one at a time into a human BST where students stand and point left or right to indicate child nodes. After building the tree, students trace in-order traversal by walking through the structure, physically experiencing that it produces sorted output.

Explain the properties that define a Binary Search Tree (BST).

Facilitation Tip

During Human BST Construction, assign each student a number card and direct them to stand where their value fits relative to already-placed peers, enforcing the ordering property out loud.

What to look for

Provide students with a list of numbers (e.g., 50, 30, 70, 20, 40, 60, 80). Ask them to draw the resulting Binary Search Tree. Then, ask them to write down the sequence of values visited during an in-order traversal.

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

Activity 02

• Think-Pair-Share
• 20 min · Pairs

Think-Pair-Share: Worst-Case BST Analysis

Present two BSTs built from the same data set: one from random insertion order (reasonably balanced) and one from sorted insertion order (completely degenerate, forming a linked list). Students individually analyze the search efficiency of each, compare with a partner, and the class discusses why insertion order matters so much.

Analyze the efficiency of insertion, deletion, and search operations in a BST.

Facilitation Tip

For Worst-Case BST Analysis, ask pairs to compare their trees after inserting the same sorted sequence, then have them present the height difference to the class.

What to look for

Pose the question: 'Imagine you have a BST containing 1000 sorted names, and you want to find a specific name. How many comparisons might you expect to make in the best case and the worst case? How does this compare to searching in a simple, unsorted list?'

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

Activity 03

• Peer Teaching
• 30 min · Small Groups

Guided Problem Solving: BST Operations Trace

Small groups receive a BST diagram and a sequence of operations (insert 5 values, delete 2, search for 3). Each group traces the tree state after each operation on whiteboards, then compares results with another group to check accuracy and discuss any discrepancies in their traces.

Construct a BST from a given set of data and trace its traversal methods.

Facilitation Tip

In BST Operations Trace, give each group a mini-whiteboard to diagram the three deletion cases, rotating roles so every student sketches one case.

What to look for

On a slip of paper, have students define 'Binary Search Tree' in their own words and list one advantage of using a BST over a simple array for searching.

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

Activity 04

• Case Study Analysis
• 25 min · Small Groups

Case Study Analysis: When BSTs Break Down

Groups analyze simplified examples of applications that used unbalanced BSTs and experienced performance degradation. Each group proposes a solution (self-balancing BST, different data structure) and the class discusses the engineering decision of when a plain BST is the right choice versus when a self-balancing variant is warranted.

Explain the properties that define a Binary Search Tree (BST).

Facilitation Tip

In When BSTs Break Down, have students annotate a poster with red arrows to show where the tree no longer supports efficient search after repeated insertions.

What to look for

Provide students with a list of numbers (e.g., 50, 30, 70, 20, 40, 60, 80). Ask them to draw the resulting Binary Search Tree. Then, ask them to write down the sequence of values visited during an in-order traversal.

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

A few notes on teaching this unit

Teachers should start with physical models before code to avoid the common trap of letting students memorize operations without understanding the invariants. Emphasize balance early; research shows students grasp O(log n) only when they feel the pain of O(n). Avoid rushing to asymptotic notation—let students measure heights and comparisons firsthand.

By the end of these activities, students should be able to construct a BST from a list, trace search and delete operations, and explain why balance matters. They will also recognize when a BST degenerates and justify why a different data structure may be needed.

---

Watch Out for These Misconceptions

• During Human BST Construction, watch for students who treat the tree as a general binary tree rather than enforcing the ordering property.

  Pause the activity and ask the class to verify whether every left child is indeed less than its parent and every right child is greater, guiding them to restate the rule aloud before continuing.

• During Worst-Case BST Analysis, watch for students who assume all BSTs provide O(log n) performance regardless of insertion order.

  Have pairs measure the height of their trees after inserting a sorted sequence and compare it to a balanced example you provide, then ask them to explain why the difference matters for search time.

• During BST Operations Trace, watch for students who skip the deletion cases with two children, treating deletion as simply removing the node.

  Ask each group to present their diagram of the third case and explain why finding the in-order successor is necessary, correcting any oversimplifications in front of the class.

---

Methods used in this brief

• Peer Teaching
• Think-Pair-Share
• Case Study Analysis