Hands-On Data Structures and Algorithms with Python - Second Edition

Inserting nodes

One of the most important operations to implement on a binary search tree is to insert data items in the tree. As we have already discussed, regarding the properties of the binary search tree, for each node in the tree, the left child nodes should contain the data less than their own value and the right child nodes should have data greater than their value. So, we have to ensure that the property of the binary search tree satisfies whenever we insert an item in the tree.

For example, let's create a binary search tree by inserting data items 5, 3, 7, and 1 in the tree. Consider the following:

1. Insert 5: We start with the first data item, 5. To do this, we will create a node with its data attribute set to 5, since it is the ...