How to Add to a Binary Search Tree by Danny Reina
Difficulty: Easy-Medium
Intent
To understand what a binary search tree is and what it can do or why even use it we first have to understand what a basic tree structure is. We will start with some basic terminology and a tree example. Additionally, I will be showing you how you can add one of the three basic properties of a BST. The three properties are add, findand remove. This article will be showing you how to write the add property in an iterative fashion. Stay tuned to subsequent articles on find and remove which will cover those methods in-depth along with an overall time-space complexity analysis of a BST.
Basic Tree Terminology & Example
Node: A structure on the tree that holds a value.
Root Node: The very first top-level node on a tree or subtree.
Subtree: A nested tree. Note. That the sub tree’s root node is not the main tree root node.
Parent Node: a node that has children nodes.
Child Node: A node that has a parent node.
Leaf: A node that has a parent node but no children nodes. In other words, it represents the end of a tree.
To understand why we imploy tree structures let's envision a few real-life applications. The elements that are rendered on this web page are formatted into a tree structure. Our root element/node would be the HTML element which then has a body node and a head node. The head node then has several nested child nodes such as a title node, meta nodes, etc. The body node also contains several nested child nodes such as div nodes, script nodes, etc.
Another situation in which trees are used is when we make decisions. For instance, say we have a pool of functions that are executed based on a boolean from a root function. Based on the value of that root function we would execute the child of that function. As one can surmise, trees are a common data structure that deserves astute attention.
What is a Binary Search Tree?
Let’s start with the differences between trees and BSTs.
Differences:
- BSTs is a tree for any kind of sorted data that works with any value types such as numbers, objects, strings.
- Every node has at most two child nodes.
- The left child node is always smaller than the parent node.
- The right child node is always bigger than the parent node.
Advantages
We now have more optimized ways of storing and retrieving information because of the ordered nature of a BST. For instance, say our root node is 10 and we wanted to find the node that contains the value of 15. Because we know that 15 is greater than 10 we can completely disregard the left subtree and just focus on traversing the right subtree of the root node to find 15. Simply put, it’s efficient.
It is worth noting that all value left to the root node is less than the value of the root node. Meanwhile, all the values to the right of the root node are greater than the value of the root node.
How to add to a Binary Search Tree?
Let’s add the number 15 to our binary search tree. The first thing we will do is obviously call the add or insertion method on the BST class which always starts on the root node.
From there, we start by iteratively traversing the BST and compare the value of our inserted value to the value of our current node which is the root node. In our case, we would say, is 15 >= 10.
Obviously, it is greater. So what’s next? According to our definition of a BST, we want to insert 15 to the right of 10 because a child node that holds a greater value than its parent must be placed on the right branch of the parent node. However, we can only insert a new node on a node that does not have 2 child nodes already. So we have to create another condition before moving to the next node to check if it’s an appropriate place for insertion. How do we do this? Since we know we have to traverse down the right side of 10 we can check if the right child node of 10 exists or not. If it doesn’t exist then we can insert 15 in that position. We do so with this code.
Take note that without the break statement, we run into an infinite loop case.
However, what if there is an existing node on the right branch of 10? In this case, we would simply move or reassign our currentNode position/value to the value of the upcoming existing node. We do so with this code.
Here we can continue moving down the right branch until we find an appropriate spot to insert 15. We iteratively move down the branch which if we recall started at 10, the root node, then moved to 12 and will then move to 13 since 15 is greater than 12. Ultimately, 15 will be inserted as the right child of node 13.
Let’s say we wanted to insert 9 into our BST. We see that 9 is less than 10 so we move down the left branch of 10. We encounter 8 which is less than 9 so we move down the right branch of 8. Here we encounter 9 which is equal to 9 so we move down the right side of 8 and we encounter no existing nodes. It is here where we insert 9.
What’s Next?
As mentioned above, this article’s focus is on the add property of a BST. It is a fairly simple method that basically says if the current node value is smaller than the input value then traverse the right side of the node, continue until we find an empty node. If the input is smaller than the current node then traverse the left branch of that node and continue until we find an empty node.
My next article concerning BSTs will cover the find method which will allow us to determine if a value is already in the BST. Stay tuned and happy coding!
