Tree structure basics

A quick recap on some key concepts and attributes about hierarchical data and tree structures.

A tree is a way of representing the hierarchical structure of something such as information, organisational entities, biological organisms, or geographical features.

The terminology for describing trees is drawn from two sources, which are obvious once we start looking at them:

  1. Kinship relations: parent, child, sibling, grand-child, grand-parent and so forth
  2. Biological terminology specifically around trees and bushes: roots, branches, and leaves.

The tree is composed of elements called “nodes” (shown as the rounded boxes in Figure 1, which are related to other nodes (shown as lines). A tree always has one node at the very top, called the “Root” node, which has no superior or “parent” node. All nodes derive from the root node.

The root node can have one or more “children”, and each of these top-level child nodes can have their own children and so on recursively. Nodes that have children are called “parent” nodes. The tree branches will have one or more nodes that do not have children. These are called “leaf” nodes (shown in orange in Figure 1) because they are the last structure at the end of the root and branch structure of a real tree.

The tree’s nodes all have a “level” which is an integer describing how far down the tree it is from the root node. Thus the root node is at Level 0, the top-level children are at Level 1 and so forth.

You can obtain more information on this Wikipedia page