Computing · JC 2 · Abstract Data Structures and Algorithms · Semester 1

Binary Trees and Binary Search Trees

Students will explore how 'if-then-else' statements allow programs to make decisions and respond to different conditions.

• MOE Syllabus Outcomes
• MOE: Programming - Middle School

About This Topic

Binary trees structure hierarchical data, with each node holding a value and at most two children: left and right. Binary search trees add order: values in the left subtree are smaller than the root, those in the right larger. JC 2 students analyze search, insertion, and deletion in BSTs. They determine worst-case O(n) time complexity from degenerate inputs like sorted sequences, which reduce the tree to a linear chain akin to linked list search.

This topic fits the MOE Computing curriculum's Abstract Data Structures unit in Semester 1. Students code iterative in-order, pre-order, and post-order traversals with stacks, then compare outputs: in-order lists sorted values, pre-order shows root-first structure, post-order root-last. They design an O(n) algorithm to verify BST properties by traversal and bounds checking, proving correctness through edge cases.

Active learning suits this topic well. Students construct trees with physical cards or digital tools in small groups, simulate operations step-by-step, and trace traversals collaboratively. These methods make abstract complexities visible, encourage peer debugging of traversal bugs, and build confidence in algorithm design through shared proofs.

Key Questions

1. 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.
2. Implement in-order, pre-order, and post-order traversals iteratively using a stack and compare the structural information each traversal exposes about the tree.
3. Design an algorithm to verify whether a given binary tree satisfies the BST property in O(n) time and prove its correctness.

Learning Objectives

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

Before You Start

Linked Lists

Why: Students need to understand sequential data structures and pointer manipulation to grasp how tree nodes connect and how traversals navigate them.

Stacks

Why: The iterative implementation of tree traversals relies heavily on the Last-In, First-Out (LIFO) behavior of stacks.

Basic Recursion

Why: While this topic focuses on iterative traversals, a foundational understanding of recursion helps in conceptualizing tree structures and operations.

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.

Watch Out for These Misconceptions

Common Misconception

BST operations always run in O(log n) time.

What to Teach Instead

Degenerate trees from sorted inputs cause O(n) performance, like linear search. Physical card builds let students measure path lengths visually. Group discussions connect input order to tree shape, correcting overconfidence in averages.

Common Misconception

All tree traversals produce the same node sequence.

What to Teach Instead

In-order sorts values, pre-order emphasizes roots first, post-order last. Collaborative stack simulations reveal unique outputs per order. Peer tracing exposes how each highlights different structures, building accurate mental models.

Common Misconception

Verifying BST property takes O(n log n) time.

What to Teach Instead

A single in-order traversal with bounds checks runs in O(n). Group algorithm design sessions prove this by walking skewed trees. Active sharing of proofs clarifies why pairwise checks are unnecessary.

Active Learning Ideas

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.

30 min·Pairs

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.

40 min·Small Groups

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.

35 min·Whole Class

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.

45 min·Pairs

Real-World Connections

• Database indexing systems, like those used by PostgreSQL or MySQL, often employ BSTs or their variants (e.g., B-trees) to efficiently store and retrieve records based on keys, speeding up queries for applications like e-commerce sites.
• File system structures, such as those found in operating systems like macOS's HFS+ or Windows' NTFS, can use tree-like structures to organize directories and files, allowing for rapid searching and access to data.
• Network routing algorithms may use tree structures to determine the most efficient paths for data packets to travel across interconnected networks, similar to how a BST organizes information for quick lookups.

Assessment Ideas

Quick Check

Present students with a small, pre-built binary tree diagram. Ask them to write down the sequence of values visited during an in-order traversal and a pre-order traversal. This checks their understanding of traversal mechanics.

Discussion Prompt

Pose the question: 'Imagine you are building a BST for a list of student IDs that are already sorted alphabetically. What will the structure of the tree look like, and how will this affect the time it takes to search for a student ID?' Facilitate a discussion on degenerate trees and worst-case complexity.

Exit Ticket

Give students a binary tree and ask them to write a short algorithm (pseudocode or actual code) to check if it satisfies the BST property. They should also state the time complexity of their algorithm and justify why it is O(n).

Frequently Asked Questions

What triggers worst-case O(n) time in binary search trees?

Sorted or reverse-sorted inputs create degenerate trees, flattening them into linked lists. Search, insert, delete then traverse all nodes linearly. Students spot this by building trees from sequences and timing operations; random inputs restore balance and logarithmic performance, as height stays low.

How do iterative in-order, pre-order, post-order traversals differ in BSTs?

In-order visits left-root-right for sorted output. Pre-order root-left-right suits copying tree structure. Post-order left-right-root aids deletion. Stacks mimic recursion: push children, pop for visits. Coding and tracing each shows unique info, like in-order confirming BST order.

What is an O(n) algorithm to verify a binary tree is a BST?

Traverse in-order while tracking min-max bounds: update bounds per node, flag violations. Handles skewed trees efficiently. Proof uses induction on subtrees. Pairs code, test violations like misplaced large left child, confirm via visualizers.

How can active learning improve understanding of binary trees and BSTs?

Hands-on card sorts and stack props make hierarchies tangible, as pairs build/break trees to see balance effects. Group relays for traversals speed error spotting via comparison. Collaborative verifier design with live coding fosters proof skills and retention over lectures, aligning with MOE's problem-solving focus.