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.

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 , where is the number of elements in the tree
  4. A node is a direct child of a node if is being pointed to by
  5. A node is a direct parent of a node if points to
  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