Binary Search Tree Structure

CS2 / C++

Abstract

The activity is a first introduction to binary search tree (BST) structures. The goal is to familiarize students with the structure, terminology, and invariants of BSTs to scaffold later activities that delve into efficiency, rebalancing, and applications. The material is conceptual and does not involve code. Students interpret tree sketches and learn tree terminology: node, parent, child, root, and leaf. Students invent the order invariant, and practice executing the search algorithms. Students analyze how the order invariant enables the search algorithm to avoid visiting all nodes in the tree, which is crucial for later study of logarithmic-time BST operations.

This activity was developed with NSF support through IUSE-1626765. You may request access to this activity via the following link: IntroCS-POGIL Activity Writing Program. 

• Level: Undergraduate
• Setting: Classroom
• Type: Learning Cycle
• Discipline: Computer Science
• Course: CS2 / C++
• Keywords: binary search tree, BST, node, parent, child, BST order invariant