A Recursive Forest

When we first started learning about trees in CSC148, I thought they were just another tool to help get across the concept of  recursion. It didn't occur to me how useful this data structure was on its own until we encountered binary search trees.

Binary search trees are trees with the special characteristics of allowing every node only two children with the child on the left strictly smaller than its parent and the child on the right strictly greater than its parent. Having this specification allows us to search for a value in the tree very efficiently. When checking if a number is in a binary search tree we first check to see if it is the root. If not, we compare the value of the number to whether or not it is less than the value of the root. If that is the case, we know that if the number is in the tree, it must be located in the left subtree; if not, we know that we should do the remaining checks in the right subtree. This method always eliminates half of the tree or subtree it checks giving it a runtime of O(lg(n)).

Linear search, please exit stage left.