Binary Search Tree Definition

Introduction

Before we dive into binary search trees, congratulations are in order! By reaching this point in the course, you’ve learned everything there is to know about pointers and memory management. We’ll focus on further practicing the concepts to deepen our understanding for the rest of the course.

This chapter has a dual purpose.

First we’ll learn about binary search trees (BST). A BST is a data structure that allows us to perform certain operations efficiently. Our interest in BST, as in the case of linked lists, is because they are great practice for writing pointer-intensive code.

On the other hand, it will constitute preparation for the course’s mini-project. This chapter will give you all the knowledge needed to implement a generic BST and use it inside the project to efficiently perform searching and ordering, which are common real-life problems. In the chapter, we’ll use pseudocode and focus on understanding how a BST should work. It will be your job to implement the pseudocode in dedicated playground lessons.

Use cases

Some ordering and searching operations aren’t efficient enough when implemented over arrays or lists. For example:

• Online sorting. Assume we constantly receive data and want to keep it sorted. We could use an array and sort it after each insertion, but it would be slow. A binary search tree will allow us to keep the data sorted without needing to sort after every insertion.
• Computing the minimum and maximum value over a collection of data.
• Finding the number of values or the values inside a range.
  • For example, finding how many temperatures were negative or how many temperatures were higher than 30 degrees Celsius during a year.
  • Finding all email messages received in a certain period.
• Finding the closest value to another value. For example, finding your colleague with the closest age to yours.

All these topics are similar in the way that they can sort huge amounts of data according to some rule. We constantly receive new data, so sorting only once is not an option. We want to maintain the data in sorted order and efficiently perform various queries over it. Here, efficiency means that we do not want to check all the elements all the time. We want to exploit the natural sorted order of the elements and perform the operations as fast as possible.

Definition

A binary search tree is a linked data structure.

• We call it a tree because it looks like an upside-down tree. It has a root node and keeps expanding downwards.
• We call it a binary tree because each node can have at most two children (could be two, could be one, could be none).
• We call it a binary search tree because all the values in the left subtree are smaller than the root’s value. All the values in the right subtree are bigger than the root’s value.

Let’s look at the following illustration.

• The tree’s root is the node with the value 2.
• Node 2 has two children—node 1 (left child) and node 3 (right child).
• The left child is smaller than the root (1 < 2, and the right child is bigger than the root (3 > 1).
• The nodes 1 and 3 are leaves. They don’t have any children. We can assume their children are NULL.