Series #1: Insert and Contains Operations
Binary Search Trees are a popular tree data structure in the Computer Science field. They prove to have a consistent O Notation for inserts, deletes, and other operations, it all depends on the number of nodes in the tree (O(n)). They are also popular as interview questions for coding interviews. Overall, I recently learned about them and thought it would be fun to share a brief series on them. For this initial post, I will be talking about the Insert Operations and the Contains Operations.
Before we dive into the operations, you must first know what a BST node contains. Specifically, they have a value, and a left child and a right child (the children can be None/Null values). Second, you must know that a BST has 2 main properties: what does it mean when a node is on the left, and what does it mean when the node is on the right. These properties can be interpreted slightly differently, but I will use these two properties: 1.) Left Node Values are Less Than the Parent Node Value, and 2.) Right Node Values are Greater Than or Equal to the Parent Node Value.
Now we are ready to start building this tree and enhancing it with the Insert and Contains Operations. In this series, I will be utilizing Python, but the code should require slight modifications to run in other languages.
To start, we are going to have our BST be constructed in a Python class with the three values we talked about in the previous paragraph: value, left child, and right child. These values will be inserted into the __init__ method and there will be inputs for only the value. This will look like this:
Now we will want to first construct our Insert Operation. This insert method will take a self variable, and an insert value integer. This operation can be done recursively, but you can speed up your method by doing it in an infinite While loop. So we will create an infinite while loop, and will check in an if statement if the current node, which starts as the root node, is less than or greater than or equal to the value that we want to insert. If the value is less than the current node, we want to then check if the current node’s left child is null, if it is not null we will set the current node as the left child node of the current node and we will then loop through the while statement again. If it is null, then we have found our insertion spot, and we will insert a BST node instance containing the insert value. After that, we will break out of our infinite while loop and will return the self instance. If the value is greater than or equal to the current node’s value, then we will do the same thing as we did above, but checking opposite child values. Specifically, we will check if the right child is null, and if it is not then we will set the current node to the right child node and will loop through the while loop again. If it is null, we will insert our value as a BST node instance and will break out of the for loop and return our self instance.
The code for the Insert Operation can be seen below:
Now we want to construct our second operation, which is the Contains Operation. This simply checks to see if an inputted value is contained in the BST; if it is then return True, otherwise return False. This is rather easy to set up. We will set up a while loop saying that it will break when the current node is null, which starts at the root node. In this loop it will check whether the insert input value is less than the current node value, if it is then the current node is equal to the current node’s left child. If it is not less than, but rather greater than the current node, then we will do the opposite and set the current node as the current node’s right child. If the iteration fails the above scenarios, it must be equal to the input value, so then you will return True since the BST contains that value. Lastly, if you loop through the whole BST and find nothing, then you will return False.
The code for the Contains Operation can be seen below:
Below are some example tests that you can run to verify that you BST Class and Insert and Contains operations work correctly:
This was an introduction to BSTs, specifically the Insert and Contains operations for a BST. In the next post we will look further into another operation, which proves to be complex, the Remove Operation. I hope you enjoyed reading about BSTs, Happy Coding!
