...

/

Introduction - Insertion and Search

Introduction - Insertion and Search

In this lesson, you will learn how to implement Binary Search Trees in Python and how to insert and search elements within them.

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:

Insertion

Let’s see how we can insert elements in a binary search tree. In the illustration below, we have an array of elements where we want to insert all the elements one by one into the binary search tree. The way we go about insertion is to start from the root node and compare the new value to be inserted with the current node’s value. If the new value is less than the value of the current node, then the new value must be inserted in the left subtree of the current node. On the other hand, if it’s greater, it must be inserted in the right subtree to satisfy the BST property. We keep comparing the values as we traverse the tree and insert wherever we find a null position.

Insertion of a Reverse Sorted List

Let’s see what happens if we insert elements from a reverse sorted list one by one in a binary search tree.

As you can see, we end up with a linear sort of a binary search tree. In such a case, if you want to find node 1 in the above binary search tree, you might have to traverse down. However, if you have a structure other than the linear one, then you can substantially cut down the number of operations that you would have to do to find node 1. We will look at that sort of a structure when we cover searching. The linear binary search tree is a structure we want to avoid when we perform operations on binary search trees because it kills the purpose of having a binary search tree. If you’re curious about how you can prevent getting the structure from reading data and forming a binary search tree ...