## Summary

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(log_{2}*N*) 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).