Trees

All three structures we looked at in the previous section have something in common – they can be represented by a list. We can start at one side (the head of the queue, the top of the stack), follow a structure in which each item is connected to the next item only, and arrive at the end (the tail of the queue, the bottom of the stack). This simplicity makes them easy to implement but also causes them to not be very performant. Adding and removing elements at the end of the list is fast, while access and search operations are quite slow.

The structure we’ll talk about now is quite different. It can be simple or it can be complex, but most importantly, it can be balanced – not too simple and not too complex, not extremely fast but also never very slow. As you may already have guessed from the section heading, this structure is called a tree.

A tree can be very easily defined by using recursion. A tree is either one of the following:

• An empty tree...