## Tree data structure versus tree data type

In fact, there is both a tree data type as well as a tree data structure, and the two are quite different. So before we go any further, it is important to make a distinction between a tree data structure and a tree data type.

For starters, a data type is only an arrangement of data without any definition of how a collection of that data is to be implemented. On the other hand, a data structure is precisely concerned with detailing how to take a particular data type and create a usable, concrete implementation of that type.

In the case of trees, a tree data type must have a value and some concept of children where each of those children is also a tree. A tree data structure is a group of nodes that are linked according to the pattern of a tree data type.

The two diagrams following show the two types of tree:

Ordered Tree:

Unordered Tree:

Therefore each node is a tree, with the potential for child nodes that are also trees. In this chapter, we will be...