Lecture Preview: Binary Search Trees (BSTs)

(Suggested book reading: Programming Abstractions in C++, Chapter 16, section 16.2)

Today we'll learn about a specific species of binary tree called a binary search tree. or BST. All the usual rules and terminology about binary trees apply, with an additional order property (constraint). For every node T:

  • every element of T's left subtree contains data less than R's data
  • every element of T's right subtree contains data greater than R's data

BST example

This document and its content are copyright © Marty Stepp and Julie Zelenski, 2019. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.