Binary Search Trees

Many different kinds of tree-based data structures exist, 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 a lesser value than itself, which is depicted using a left arrow, and one child with a greater value than itself, which is depicted using a right arrow.

Additionally, notice that all of the 50’s left descendants are less than it. At the same time, all of the 50’s right descendants are greater than it. The same pattern goes for each and every node.

While the following example is a binary tree, it’s not a binary search tree:

It’s a binary tree because each node has zero, one, or two children. But it’s not a binary search tree, because the root node has two left children; that is, it has two children than are less than it. For a binary search tree to be valid, it can have at most one left (lesser) child and one right (greater) child.

The implementation of a tree node in Python might look something like this:

We can then build a simple tree like this:

Because of the unique structure of a binary search tree, we can search for any value within it very quickly, as we’ll now see.