A simple binary tree, as shown earlier in Figure 6.2, is the most complex data structure discussed in this chapter. This type of binary tree is made up of nodes that contain a piece of information and pointers to left and right child nodes. In many cases, you’ll use binary trees to store data in a sorted manner: as you add a value, you’ll look at each existing node. If the new value is smaller than the existing value, look in the left child tree; if it’s greater, look in the right child tree. Because the process at this point is the same no matter which node you’re currently at, many programmers use recursive algorithms to work with binary trees.
Why use a binary tree? Besides the fact that finding items in a binary tree is much faster than performing a linear search through a list or an array, if you insert the items in an ordered fashion, you get not only efficient storage, but sorting for free—like finding a prize in the bottom of your cereal box! Who could ask for more? You’ll see this technique at work in the sample module, TREETEST.BAS.