If you are a beginner programmer, chances are you may have heard of the term “Binary Search Tree”, without knowing what it really means. A Binary Search Tree (BST) is what we call a data structure, which allows us to store and access information in a much more efficient and organized manner.
The formal definition of a tree (not BST) is as follows (taken from Wolfram MathWorld): “A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph”. The points at which the line segments connect in a tree are called nodes. For any given node n, the nodes which are connected “below” are called children and the node which connects to n from above is called the parent node. Each of the nodes in a tree has an associated value, sometimes called the “key”. A BST is such a tree where each node has a maximum of 2 children and where the key values for the left and right children are smaller and larger than the current (or “root”) node, respectively. Here is an example of a BST:
So now that you know what a BST is, you might be wondering, what’s the point of using it? Well, because of the way it is structured, it allows you to search for data significantly faster than if you were to store it in say, a simple 1-dimensional array. Here’s an example: Say you wanted to find some node with a key value of k in the above tree. How would you go about doing so? We can do a binary search on the tree, greatly reducing our search space at each iteration. We start at the root node (with a value of 8), and compare it to the value of k. If it is greater than k, we move over to the left child of the root; if it is smaller, then we move over to the right child. Every time we check a node, we reduce the amount of nodes we have left to check in half; this gives us an average runtime of O(log n), where n is the number of elements in the tree. If we were to have stored all of our data in an linear array, our average runtime to search for a piece of data would be O(n), where n is the number of elements in the list. Other operations such as deletion and insertion also share the same runtime of O(log n) when using a BST.
