Data Structures in Ruby: Binary Search Tree — Part II

…and, an introduction to recursion methods

Last week we began our introduction into the binary search tree. In Ruby, we set-up our Node Class and our BinarySearchTree Class and implemented the #insert method. Today, we are going to code the #find method which will give us some better insight into how a binary search tree is traversed. However, today we will also begin to look at a method using recursion.

First, a brief recap: A binary search tree is a data structure that is organized in such a way that each element (or Node) contains no more than two child nodes (hence the term “binary”). The structure also must adhere to the rule that of the two children, the one that is smaller than the parent is to the left and the one that is larger than the parent is to the right. This process repeats itself down the tree. What makes this such a great data structure is the fact that any value can be found quickly merely by following the rules. For example, if a tree had 5 as its root node, and we were looking for the number 8, we immediately can eliminate every part of the tree to the left of the root. In other words, half of the tree does not have to be searched. Every level that you go down, you remove another half. This makes for very efficient searching, provided the tree is at least somewhat balanced.