Introduction - Insertion and Search

In this lesson, we will go over the binary search tree data structure. We will first cover the general idea of what a binary search tree is and how one may go about inserting data into this structure as well as how one searches for data. Once we cover the general idea, we will move over to the implementation of the binary search tree data structure in Python. We will construct two class methods that will implement the search and insertion algorithms.

A binary search tree is a tree data structure in which nodes are arranged according to the BST property which is as follows:

The value of the left child of any node in a binary search tree will be less than whatever value we have in that node, and the value of the right child of a node will be greater than the value in that node.

Note: If there aren’t exactly two children, the reference to the non-existent child will contain null value.

This type of pattern persists throughout the tree. Let’s look at an example illustrated below: