Terminology

Let’s consider some of the terminology associated with tree data structures.

To understand trees, we need to first understand the basic concepts related to them. A tree is a data structure in which data is organized in a hierarchical form.

Figure 6.1 contains a typical tree consisting of character nodes lettered A through to M:

Figure 6.1: Example tree data structure

Here is a list of terms associated with a tree:

• Node: Each circled letter in the preceding diagram represents a node. A node is any data structure that stores data.
• Root node: The root node is the first node from which all other nodes in the tree descend from. In other words, a root node is a node that does not have a parent node. In every tree, there is always one unique root node. The root node is node A in the above example tree.
• Subtree: A subtree is a tree whose nodes descend from some other tree. For example, nodes F, K, and L form a subtree of the...