In programming, we have come across BST and Hash Table applications very often. But most of the times we prefer to use hash table even if the space complexity increases.
But in this article, we will be looking into the advantages and places where we prefer to use Binary Search Trees over Hash Table. Let us first revisit BST and Hash table.
Binary Search Trees
A BST is a type of tree data structure where for every node, all the nodes to the left of this node have value lesser than the current node’s value and all the nodes to the right of this node has value greater than the current node’s value along with the fact that both left subtree and right subtree are Binary Search Trees.
Example:
One application of this is basically when we get a stream of incoming data and we want to arrange them systematically in a sorted order in efficient way. As BST insertion takes time.
We can also look at the insertion of elements in BST code:
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
struct node *left;
struct node *right;
};
struct node* newNode(int val){
struct node *newnode = new node();
newnode->data = val;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
node* insertIntoBST(node* root, int val) {
node *cur = root, *temp = new node(val);
while (cur) {
if (cur -> val > val) {
if (cur -> left) {
cur = cur -> left;
} else {
cur -> left = temp;
break;
}
} else {
if (cur -> right) {
cur = cur -> right;
} else {
cur -> right = temp;
break;
}
}
}
return root ? root : temp;
}
bool checkBST(node *root,node *l,node *r){
if(root == NULL)return true;
if(l && root->data <= l->data)
return false;
if(r && root->data >= r->data)
return false;
return checkBST(root->left,l,root) && checkBST(root->right,root,r);
}
void travel(node *root){
if(root){
travel(root->left);
cout<<root->data<<" ";
travel(root->right);
}
}
int main() {
// your code goes here
struct node *root = newNode(4);
root = insertIntoBST(root,1);
root = insertIntoBST(root,2);
root = insertIntoBST(root,3);
root = insertIntoBST(root,5);
root = insertIntoBST(root,6);
//travel(root);
//Check this condition before moving forward
//I have considered that the tree is not given in BST
vector<int> arr;
int n = arr.size();
for(auto e : arr)cout<<e<<" ";
cout<<endl;
travel(root);
return 0;
}
Even Searching for a key in Binary Search Tree takes 0 (logn) time. Let us see the snippet of searching a key in BST.
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
struct node {
int val;
node *left;
node *right;
node() : val(0), left(nullptr), right(nullptr) {}
node(int x) : val(x), left(nullptr), right(nullptr) {}
node(int x, node *left, node *right) : val(x), left(left), right(right) {}
};
node* searchBST(node* root, int val) {
if(!root) return nullptr;
if(root->val == val) return root;
return root->val > val ? searchBST(root->left, val) : searchBST(root->right, val) ;
}
int main() {
struct node *root = newNode(4);
root = insertIntoBST(root,1);
root = insertIntoBST(root,2);
root = insertIntoBST(root,3);
root = insertIntoBST(root,5);
root = insertIntoBST(root,6);
node *ans = searchBST(root,3);
if(ans!=NULL)
cout<<ans->val<<endl;
else cout<<"Not Found";
return 0;
}
Similarly, Binary Search Tree supports deletion operation too in time. Now let us talk about Hash Table.
Hash Table
It is a type of data structure which stores pointers to the corresponding values of a key-value pair. This acts huge memory storage of key-value pairs where any item can be accessed in constant time although the memory usage is high. It uses a Hash Function which handles collisions and uniformly distributes the keys over the memory. All insertion, searching, deletion operations can be done in constant time.
Let us see one popular example of four sums to target problem where an array of elements if given we have to find a group of four elements whose sum is the target sum.
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n=nums.size();
sort(nums.begin(), nums.end());
int a,b,c,d;
int now;
vector<vector<int>>result;
map<vector<int>, bool>hash;
for (a=0; a<n; a++) {
for (b=a+1; b<n; b++) {
c=b+1;d=n-1;
while(c<d) {
now=nums[a]+nums[b]+nums[c]+nums[d];
if (now<target) {
c++;
}
if (now>target) {
d--;
}
if (now==target) {
vector<int>temp;
while (c<d&&nums[c]==nums[c+1]) c++;
while (c<d&&nums[d]==nums[d-1]) d--;
temp.push_back(nums[a]);
temp.push_back(nums[b]);
temp.push_back(nums[c]);
temp.push_back(nums[d]);
if (hash.count(temp)) {
c++;
continue;
}
result.push_back(temp);
hash[temp]=true;
c++;
}
}
}
}
return result;
}
int main(){
int n;
cin>>n;
vector<int> nums;
for(int i = 0;i<n;i++)cin>>nums[i];
int target;
cin>>target;
vector<vector<int>> ans = foursum(nums,target);
for(auto v : ans){
for(auto ele : v)cout<<ele<<" ";
cout<<endl;
}
return 0;
}
So now we have arrived at the point where we know the proper uses of these two data structures, so we can now discuss when to prefer Binary Search Trees. Let us go back to our BST created by our programme.
If we do InOrder traversal of this BST [1,2,3,4,5,6] we will get a sorted list of values which is not the case in Hash Table naturally.
When we have to find nearest successor, Least Common Ancestors etc. types of problems where we require the property of BST, we cannot use Hash Table as it will complicate and increase the time complexity.
In Binary Search Trees we don’t have to deal with collisions due to same keys inserted again and again whereas the average time complexity of a hash table arises due to collision handling of the hash functions. Hash Table and hash maps generally are cumbersome to customize as we directly use the library functions for those whereas BST is quite easily customisable and hence scalable. P.s. Just an example 🙂
Multilevel Hashing that is common in Database Storage Architectures uses this for indexing with huge memory blockage.
- Hash Table has moreover lesser security in smaller architectures as the hash function is susceptible to manipulation and if used to make unnecessary collisions which will, in turn, result in more time complexity.
- Hash Tables are time-consuming when we have to do range queries whereas Binary Search Trees can efficiently handle range queries.
- Hash Tables are not good for indexing as we can see above multilevel indexing will waste a lot of extra memory and hence most of the time B & B+ trees are used in database architectures.
If we want to find the predecessor or successor of a node in a hash table, we have to maintain a parent of every node and then traverse to all those nodes one by one which will take more time than which is the used time complexity of Binary Search Tree in this case.
Data Migration in terms of Hash Table is very costly as the whole static memory has to be transferred even if some keys don’t contain any values whereas Binary Search Trees can literally build the whole tree in logarithmic time and multiplied by the number of elements being inserted which is more efficient.
Hence, we can see that in most of the practical situations we use a Binary Search Tree rather than a Hash Table to reduce the space complexity and easy scalability of the data structure. Hope this article is useful to aspire developers and programmers. Do share this article if you find this worth a read.
Don’t forget to check out the courses by Coding Ninjas.
By Mridul Kumar
