Binary Trees and Binary Search Trees

Binary trees and BSTs rely on spatial reasoning and precise ordering, so hands-on activities let students see how structure affects function. Physical manipulation of cards or stack tokens makes abstract properties visible and measurable, which builds lasting mental models.

• JC 2
• Computing
• 4 activities
• 30 min–45 min

Learning Objectives

1. Analyze the worst-case time complexity of search, insertion, and deletion operations in a Binary Search Tree (BST).
2. Implement iterative in-order, pre-order, and post-order tree traversals using a stack data structure.
3. Compare the output and structural insights gained from in-order, pre-order, and post-order traversals.
4. Design an algorithm to verify if a given binary tree adheres to the BST property within linear time.
5. Explain the degenerate input that leads to a BST's worst-case performance and its equivalence to linear search.

Think-Pair-Share

⏱ 30 min·Pairs

Card Build: BST Insertion

Provide number cards to pairs. Students insert cards one by one into a physical BST layout on desks, drawing lines for child pointers. They search for a target number, noting path length, then rebuild with sorted cards to observe degeneration. Pairs record time complexities.

Prepare & details

Analyse the worst-case time complexity of search, insertion, and deletion in a binary search tree, identify the degenerate input that triggers it, and explain why it is equivalent to linear search.

Facilitation Tip: During Card Build, circulate with a ruler to measure path lengths and ask students to compare their tree heights to group averages.

Setup: Standard classroom seating; students turn to a neighbor

Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs

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

Think-Pair-Share

⏱ 40 min·Small Groups

Stack Relay: Tree Traversals

Print tree diagrams for small groups. Use paper stacks as props to simulate iterative traversals: push/pop nodes per order. Groups race to list visit sequences on whiteboards, then compare results. Discuss structural insights each order provides.

Prepare & details

Implement in-order, pre-order, and post-order traversals iteratively using a stack and compare the structural information each traversal exposes about the tree.

Facilitation Tip: For Stack Relay, assign roles so every student places one node, then have the team trace outputs together before moving to the next order.

Setup: Standard classroom seating; students turn to a neighbor

Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs

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

Think-Pair-Share

⏱ 35 min·Whole Class

Bounds Check: Verify BST

Whole class uses shared online tree visualizer. Students input trees, trace a partner-designed O(n) verifier algorithm checking min-max bounds during in-order traversal. Vote on correctness for skewed cases, adjust code live.

Prepare & details

Design an algorithm to verify whether a given binary tree satisfies the BST property in O(n) time and prove its correctness.

Facilitation Tip: During Bounds Check, provide a sheet with bounded boxes so students literally draw the valid range for each subtree.

Setup: Standard classroom seating; students turn to a neighbor

Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs

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

Think-Pair-Share

⏱ 45 min·Pairs

Complexity Pairs: Op Simulations

Pairs code simple BST ops in Python, test random vs sorted inputs with timers. Graph search times, identify degenerate triggers. Swap codes to debug and verify O(n) worst case.

Prepare & details

Analyse the worst-case time complexity of search, insertion, and deletion in a binary search tree, identify the degenerate input that triggers it, and explain why it is equivalent to linear search.

Facilitation Tip: Run Complexity Pairs by timing students on the same operation with different inputs, then graph results to reveal performance trends.

Setup: Standard classroom seating; students turn to a neighbor

Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs

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

Teaching This Topic

Start with physical builds before any code; research shows this reduces confusion between tree shape and traversal order. Avoid rushing to asymptotic analysis—let students experience O(n) with their own skewed trees first. Emphasize that BSTs are tools for ordering, not just containers, by connecting to real search problems like student ID lookups.

What to Expect

Students will confidently trace insertions, traversals, and checks by the end of the activities, explaining why skewed trees slow searches. They will articulate time complexities using concrete examples from their own work.

Watch Out for These Misconceptions

Common Misconception

During Card Build BST Insertion, watch for students assuming all BSTs stay balanced regardless of input order.

What to Teach Instead

Ask groups to insert a sorted list into their cards and measure the path length to the last node, then compare it to a random insertion sequence to reveal the impact of input order.

Common Misconception

During Stack Relay Tree Traversals, watch for students believing pre-order and in-order always produce the same sequence.

What to Teach Instead

After each relay, have the group trace their stack outputs side by side and label the root visits to highlight why the orders differ.

Common Misconception

During Bounds Check Verify BST, watch for students checking each node against all ancestors rather than using bounded ranges.

What to Teach Instead

Provide a sheet with bounded boxes for each subtree and have students write the valid range inside each box before verifying values, which makes the O(n) property visible.

Assessment Ideas

Quick Check

After Card Build BST Insertion, give each student a small pre-built tree diagram and ask them to write the insertion sequence for a new value, explaining why the path takes the shape it does.

Discussion Prompt

During Card Build BST Insertion, pose the question: 'If your tree becomes a straight line after inserting IDs in alphabetical order, how would search time change compared to a balanced tree?' Use the card trees to illustrate worst-case performance.

Exit Ticket

After Bounds Check Verify BST, ask students to write a short algorithm to check the BST property and state its time complexity, justifying why it is O(n) using their bounded box diagrams as evidence.

Extensions & Scaffolding

• Challenge groups to design an algorithm that rebalances a BST after insertions, using their card trees as test cases.
• For students struggling with traversals, give them a partially completed stack diagram and ask them to finish the sequence step by step.
• Deeper exploration: invite students to compare BST performance with hash tables on a fixed dataset by timing searches in both structures.

Key Vocabulary

Binary Tree	A tree data structure where each node has at most two children, referred to as the left child and the right child.
Binary Search Tree (BST)	A binary tree where for each node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value.
Traversal	The process of visiting each node in a tree exactly once, in a systematic order (e.g., in-order, pre-order, post-order).
Degenerate Tree	A tree where each node has only one child, resulting in a structure resembling a linked list.
Time Complexity	A measure of the amount of time an algorithm takes to run as a function of the length of the input, often expressed using Big O notation.