A tree consists of nodes with a parent-child relationship. Each node has a parent (except for the first node at the top) and zero or more children:

The top node of a tree is called the root (11). It is the node that does not have a parent. Each element of the tree is called node. There are internal nodes and external nodes. An internal node is a node with at least one child (7, 5, 9, 15, 13, and 20 are internal nodes). A node that does not have children is called an external node or leaf (3, 6, 8, 10, 12, 14, 18, and 25 are leaves).

A node can have ancestors and descendants. The ancestors of a node (except the root) are parent, grandparent, great-grandparent, and so on. The descendants of a node are child, grandchild, great-grandchild, and so on. For example, node 5 has 7 and 11 as its ancestors and 3 and 6 as its descendants.

Another terminology used with trees is the subtree. A subtree consists of a node and its descendants. For example, nodes 13, 12, and 14 consist a subtree of the tree from the preceding diagram.

The depth of a node consists of the number of ancestors. For example, node 3 has depth 3 because it has 3 ancestors (5, 7, and 11).

The height of a tree consists of the maximum depth of any node. A tree can also be broken down into levels. The root is on level 0, its children are on level 1, and so on. The tree from the preceding diagram has height 3 (maximum depth is 3 as shown in the preceding figure—level 3).

Now that we know the most important terms related to trees, we can start learning more about trees.