A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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 ...