Member-only story
How to Implement a Binary Search Tree
A binary search tree, or BST, is a type of data structure typically used to organize data. It is structured in a very different way compared to stacks, queues and lists. Generally, a BST will have the following properties.
1. The tree has a root node that is used as the starting point for any operation
2. Each node in the tree has one or two nodes attached to it. One is to the right of the node, and the other is to the left.
3. Everything to the right of a node is larger in value compared to it. Everything to the left of a node is smaller in value compared to it.
The main valuable property of BSTs is that they store data in a way that is easy to search. When data is stored in a BST, we can use the property of left and right nodes to determine where a node we are searching for is likely to be. In general, it takes less time to search a BST compared to searching through a list of values one by one.
To start implementing a tree, we first need to create a new type of node that has a left and right property. This node object isn’t too different from the node objects used for lists. The only difference is that the new node object has two links instead of one. It still has a value, and still implements the same getters and setters to manipulate its values.
