# Comparison between Hash Table and Binary Search Tree

In this article we are going to see the **comparison between the two different data structures hash table and Binary search tree**.

Submitted by Radib Kar, on September 19, 2020

## Comparison b/w operation in hash table & Binary Search Tree

**Insertion:**Insertion in a hash table is less expensive that insertion in a Binary Search Tree. Insertion in hash table in O(1) which is constant time whereas insertion in a Binary search Tree is O(logn)( Considering the self-balancing BST).**Deletion:**Deletion in a hash table is less expensive that deletion in a Binary Search Tree. Deletion in hash table in O(1) which is constant time whereas deletion in a Binary search Tree is O(logn)( Considering the self-balancing BST)**Searching:**Searching in hash table is also less expensive as searching in BST is also of logarithmic complexity but hash table has constant time complexity.**Sorting**Inorder traversal of the BST produces a sorted list. Hash table doesn't guarantee any such sorted list.(Don't think about map, map is not a hash table, map is actually implemented with self-balancing tree).

Operation | Hash table | Binary Search Table |
---|---|---|

Insertion | O(1) | O(logn) |

Deletion | O(1) | O(logn) |

Search | O(1) | O(logn) |

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.