Binary Search Tree (BST)

A fundamental ordered data structure used throughout CS400

What Is a BST?

A Binary Search Tree stores keys so that for every node, keys in the left subtree are smaller and keys in the right subtree are larger. This ordering enables efficient search, insert, and delete.

Binary Search Tree Diagram
Tip: Balanced BSTs keep operations fast on average.

Core Operations

  1. Search: Compare the key and move left/right until found or null.
  2. Insert: Search to a null spot, then attach a new node there.
  3. Delete: Handle 0, 1, or 2 children (with successor replacement for 2).

Learn More

For a deeper dive, see the Binary Search Tree article on Wikipedia .