Tree (Data Structure)

Topics: Data Structure

---

A tree is a non-linear and dynamic data structure. It’s dynamic since its structure can change during the execution of a program, and it’s non-linear since each of its elements can be followed by more than one element.

Other definitions

A tree can also be called a hierarchical data structure that contains a collection of elements called nodes, one of them known as root. Between all of these elements, parent-child relations are established.

At the same time, trees are homogeneous structures defined by the concatenation of one node element along with a finite number of disjoint trees called sub-trees.

As with lists, stacks and queues, trees can be contiguous (which use arrays) or linked (which use pointers). Despite that, trees are commonly linked since they are a dynamic data structure.

A binary tree is a special type of tree that is used to save up memory and space, since trees that contain nodes each with a different number of offspring can waste a lot of memory and space.

Graphical representation §

Graphically, trees can be seen as a graph with the following features:

1. Every non-empty tree has one and only one root node
2. Loops can’t exist
3. The number if lines is always $n-1$, where $n$ is the number of elements in the tree
4. A node $X$ is a direct child of a node $Y$ if $X$ is being pointed to by $Y$
5. A node $X$ is a direct parent of a node $Y$ if $X$ points to $Y$
6. Every node that has no children is called a terminal or leaf
7. Every node that isn’t the root node nor a terminal node is known as an interior node
8. The degree of a node is the number of direct offspring of a node. The degree of the tree is the maximum degree among all the node degrees
9. The level is the amount of links that have to be traversed to reach a certain node plus one. By definition, the root node has a level of 1
10. The height of a tree is the maximum number of levels among all the levels within the tree