Binary Search Tree — the Swiss Army knife of data structures
I am going to explore the binary search tree (BST). This is a visualization of the structure of a BST:
The BST is a tree data structure, its distinction being that each node can only have at most two children. One child’s value will always be less than the parent’s value and the other child’s greater. Left or right, it will be consistent throughout the structure. For the pictured example, the left children are less than their parent and the right are greater. Operations can be completed in O(log n) time complexity since the data set is constantly being halved until the solution is reached.
Let’s compare it to the Hash Table structure with some O(n) time complexity operations. Obviously insertion & retrieval are not a contest. But how does one list all elements of a data set in order with a HT, not easily nor quickly. Finding the nearest value to an search input and the HT becomes O(n). How about listing a data set in-order? An easy exercise in recursion with a BST. Also a HT requires that memory be allocated for the structure even if it is not all currently being used.
The BST works well as an all-round data structure, not the best nor the worst, the Swiss Army knife of data structures.