Member-only story
Data structures — Binary Search Trees
An introduction to Binary Search Trees and some common methods for this data structure.
What are Binary Search Trees?
Binary Search Trees is a type of data structure to store data in an ordered way. This data structure consists of nodes, and each node has at most two child nodes. The order of these nodes follow a property called the BST property. The BST property states that the value of a left child node is less than it’s parent, and the right child node is greater than it’s parent. This property allows for fast operations, to which most of them fall within O(log(n)).
An example of a binary search tree can be found above. The node at the top is called the root node because it does not have any parents. If you follow each node, you’ll see that they all follow the BST property.
Time Complexities of common operations in Binary Search Trees
- Search — Average: O(log(n)) Worst Case: O(n)
- Insert — Average: O(log(n)) Worst Case: O(n)
- Delete — Average: O(log(n)) Worst Case: O(n)
Search algorithms
There are many different ways to traverse a Binary Search Tree and they can be boiled down to three types: Post Order…
