What is a Binary Search Tree?
Stop. Before we even commence to look at understanding what this is, let’s build up a mental model first, so when the definition is presented we have some context and secondly we have a pool of terms that we can use and that makes sense. Above in the funky diagram above is a basic tree. It has a root node (parent node) and child nodes (A and F). Obviously based on context the role can change. So if we traversed the tree to Node A, it would be the parent node (not root node), with two child nodes, node B on the left and node C on the right. We can call A and F sub-trees if you will. Now that’s pretty basic.
Now consider the same tree above, but instead of letters we insert numbers. Now what’s interesting to note, that the value of all nodes in the left subtree is lesser or equal than the value of all nodes in the right subtree.
LEFT => Let’s check quickly, 10 (parent) + 8 (left child) + 12 (right child) = 20.
RIGHT => 20 (parent) + 17 (left child) + 25 (right child) = 62.
Going back to what we said above, is that true? (value of all nodes in left subtree, less or equal to value of all nodes on the right?)
20 < 62 = TRUE.
Excellent, we making progress! But, that principle should also apply to the subtrees.If we traverse left to node 10, it is parent to 8 and 12. 8 < 12 = TRUE. So there is no violation. When we traverse to the right to node 20, it is a parent to 17 and 25. 17 < 25 = TRUE. This principle is the important attribute that defines a Binary Search Tree. But there is one more!
Binary search trees in using the binary search algorithm requires “ordering” and as such, each parent node will have a value, whose children on the left, are smaller than it. On the right, will have children whose values are greater. So if we traverse and visit node 10. It has a left-node of 8 (which is < 10) and a right-node of 12 (which is > 10). The same applies if we visit node 20 on the right. Being parent, it has a left-node of 17, which is less than itself (20). And it has a right child node of 25, which is greater than itself. Awesome!
These two principles applied, is a Binary Search Tree.
Now let’s take in Wikipedia’s definition:
“In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of containers: data structures that store “items” (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.”
Before we leave off, binary search trees have a best running time of O(log n). That is really efficient algorithm, where at the growth of the input over time, the time of the algorithm wanes.