Binary Search Tree
Implementing a Binary Search Tree:
Let’s get one thing clear, if you’re going to implement a BST, the underlying assumption is that you have the values that you are trying to sort in the order that you want them to be sorted in. If you call your binary search tree function within your previous function that is sorting your array of values, chances are you will end up with a run-time of O(n log n), which nobody wants. At this stage in the game, I try to keep algorithms at O(n) if not faster.
For the most your binary search tree should have a run-time of O( log n), this is because if we are searching through an array of size n, and halving the array each time time until we get the value we want, that can be expressed as base-2 logarithm of n, AKA O(log n). Logarithm functions grow very slowly and are the inverse of exponentials, which grow very quickly. Worse case scenario you have a lot of values, the run-time is usually O(n).
Here are some charts from Khan Academy that visualize this:
Further Reading:
