A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Binary Search Trees

There are many different kinds of tree-based data structures, but in this chapter, we’ll focus on a particular tree known as a binary search tree.

Note that there are two adjectives here: binary and search.

A binary tree is a tree in which each node has zero, one, or two children.

A binary search tree is a binary tree that also abides by the following rules:

• Each node can have at most one “left” child and one “right” child.
• A node’s “left” descendants can only contain values that are less than the node itself. Likewise, a node’s “right” descendants can only contain values that are greater than the node itself.

Here’s an example of a binary search tree, in which the values are numbers:

Note that each node has one child with ...