Understanding Binary Search Tree Data Structure.
Choosing between different data structures to store data can be tricky if we don’t understand the differences between them. For instance, we can use an array or a linked list to store data, both are linear data structures that allow you to store data in a linear way. There are different advantages and disadvantages over one another.
In this article, we’ll talk about another data structure that can give you better performance than the two data structures mentioned above — I’m talking about a Binary Search Tree.
This article assumes some basic knowledge about data structures and Big O notation.
Let’s dive right into some concepts that will help us better understand what this data structure is all about.
A Binary Search Tree or BST is a specific type of tree so let’s start by defining what a Tree is.
Tree
A Tree is a non-linear data structure that is composed of nodes, where each node in the tree can have many child nodes and every node can hold some data. The first node in a tree is called the root, nodes in the same level that shared the same parent are called siblings.
What is a Binary Search Tree?
A BST is a specific type of Tree that follows certain validations. For instance, in a BST every node can have at most two children and all nodes to the left side should be less than the parent node, as well as all the nodes to the right side should be greater than the parent node.
A Binary Search Tree is not a linear data structure because there are multiple different ways to iterate a tree, since we have nodes to the left and right sides we can take different directions when iterating over the tree.
When we create a BST we usually want to iterate and list all its elements store in the tree, just like we do when using linear data structures like arrays or linked lists. This process is called tree traversal, and it means that we process the tree in a specific way that we can visit every node only one time.
Now let’s see how a BST looks like.
As I mentioned before every node to the left side is less than the parent node and every node to the right side is greater than the parent node.
Now to traverse this tree we have different options, let’s look at them one by one.
Breadth-First Traversal
When using this technique to traverse a tree we go from left to right on each level visiting each node. We start at the root node of the tree. Level Order Traversal also refers to the same traversal strategy because we go level by level visiting each node in the tree until we reach the end.
We can use this technique when looking for the shortest path between any two nodes in the tree. Implementing a Breadth-First Traversal with the help of a Queue data structure would take BigO(n).
Traversing and printing the values from the BST shown above using Breadth-First Traversal would look like this: 25, 20, 34, 15, 22, 29, 39, 27, 31.
Depth-First Traversal
There are three ways of traversing a tree using Depth-First Traversal — preorder traversal, inorder traversal, and postorder traversal.
Preorder Traversal (Root, Left, Right)
We first visit the root node, then the left node, and then the right node until we traverse the entire tree. This method is useful when we want to perform a search operation or process the root node before moving to the child nodes. Traversing and printing the values from the BST shown above using Depth-First Traversal would look like this: 25, 20, 15, 22, 34, 29, 27, 31, 39.
Inorder Traversal (Left, Root, Right)
We first visit the left node, then the root node, and then the right node until we traverse the entire tree. If we apply inorder traversal to a BST we’ll get the values in ascending order. That is something that we’ll want to achieve very often when using a tree. Traversing and printing the values from the BST shown above using Depth-First Traversal would look like this: 15, 20, 22, 25, 27, 29, 31, 34, 39.
Postorder Traversal (Left, Right, Root)
We first visit the left node then the right node, and then the root node until we traverse the entire tree. This is useful when we need to perform some operations on the child nodes first before visiting the root. Traversing and printing the values from the BST shown above using Depth-First Traversal would look like this: 15, 22, 20, 27, 31, 29, 39, 34, 25.
There are two ways of implementing any of these three methods I just mentioned above — The first one is using recursion, and the second one is using another data structure called a stack.
There are a couple of things to consider when choosing between these two techniques to iterate a BST. If you can tell that the data you are looking for is near the root node, you can go with Breadth-First Traversal, but if you know that the data you are looking for could be very deep in the tree then using Depth-First Traversal might be a better approach.
BigO Notation for a BST
So far we talked about the definition of a BST, and the different strategies to traverse it. But, what are the advantages of using a BST over a linear data structure such as an array or a linked list?. Well, everything lays down to the run time complexity we can achieve when using a Binary Search Tree in operations like insertion, deletion, and searching.
For instance, arrays and linked lists give BigO(n) in search operations, BigO(1) in insert operations, and BigO(n) in removal operations, but we can do better with BST. Now if we have a sorted array, we could perform a binary search algorithm to search for elements, and the run time complexity would be BigO(log n) which is better than using an unsorted array or a linked list.
If you haven’t heard of what the binary search algorithm is all about, let’s defined it here.
Binary Search is an effective algorithm to perform search operations over a sorted array. The way it works is that it compares the value you are looking for with the middle element in the array. If the value is greater than the middle element, the algorithm discards the left half of the array and will continue searching on the right side. If the value is less than the middle element, the algorithm discards the right half of the array and will continue searching on the left side.
But even for a sorted array, we still have BigO(n) for inserting and deleting operations. Here is when we want to use a BST because we will still have the ability to perform a binary search algorithm and have BigO(log n) for all three operations. The only thing to consider is that if we want to have always BigO(log n) in a BST we have to keep the tree balanced.
For example, if we have a BST like the following, we won’t have any advantages over using an array because the tree is not balanced.
Now let’s see how searching and inserting into a BST would look like.
As you can see to search for an element inside the tree we can just validate that the value we are looking for is less or greater than the value of the current node, and based on that move to the left or right. In this case, 14 is greater than the root node, so we move to the right, then we check if the next value is less or greater than the value we are looking for again, and this time is greater, so we move to the left. And at this point, we have found the element.
For inserting an element in a BST, we follow some similar validations, we start at the root node of the tree and validate if the value we want to insert is less than the current node value and if it is we also check if the left node is not null, if it is not null we move to the left side but if it is null we insert the value to the left of the current one. And the same applies to the right side in case the value is greater than the root node value. So in this example, we keep validating the same traversing from value 12 to 10, then to 5, and finally to 7. When we reach this point we run the same validations but this time the left node of 7 is null so we insert the value to the left side of the current node and we are done!!
Now for traversing and printing the value of each node we could use any of the three methods I mentioned above that are part of the Depth-First Traversal strategy. The run time complexity of doing this would be BigO(n) because the amount of effort to traverse the entire tree is proportional to the number of nodes we have in the tree. So just like with arrays or a linked list the run time complexity to traverse the entire tree is linear.
Conclusion
Use a BST whenever you want to optimize operations like insertion, deletion, and searching over a collection of elements. Using a BST is quite better than a linked list or array. The only advantage of using an array over a BST is the BigO(n) that arrays give when accessing an element.
We can use BST as an efficient data structure to store and search for data. The advantage of using a BST over a linked list or array is that it gives us better run time complexity.
Thank you for taking the time to read this article.
