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 R:

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

BST example

This document and its content are copyright © Marty Stepp, 2018. 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.