In this chapter, we saw how we can use a
binary tree to structure sorted information so as to reduce the
search time for any particular element. For applications requiring
direct access to the elements in a sorted structure, the binary
search tree is a very useful data type. If the tree is balanced, we
can access any node in the tree with an O(log2N) operation. The binary search tree combines the
advantages of quick random access (like a binary search on a linear
list) with the flexibility of a linked structure.
We also saw that we can implement the tree
operations very elegantly and concisely using recursion. This
result makes sense, because a binary tree is itself a "recursive" structure: Any node in the tree is
the root of another binary tree. Each time we move down a level in
the tree, taking either the right or the left path from a node, we
cut the size of the (current) tree in half, a clear case of the
smaller-caller. We also saw cases of iteration that replaced
recursion (InsertItem and DeleteItem).