# Trees

A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root. Thus, tree is a (possibly non-linear) data structure made up of nodes or vertices and edges without having any cycle. The tree with no nodes is called the **null** or **empty** tree. A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy. The following diagrams illustrate the meaning of a tree:

Each linear list is trivially a tree | Not a tree: cycle A→A | Not a tree: cycle B→C→E→D→B | Not a tree: undirected cycle 1-2-4-3 | Not a tree: 2 non-connected parts A→B and C→D→E |

**Tree terminologies:**

- We will call every circle a
**node**and each line an**edge**. Nodes “19”, “21”, “14” are below node “7” and are directly connected to it. This nodes we are called**direct descendants (child nodes)**of node “7”, and node “7” their**parent**. The same way “1”, “12” and “31” are children of “19” and “19” is their parent. Intuitively we can say that “21” is**sibling**of “19”, because they are both children of “7” (the reverse is also true – “19” is sibling of “21”).For “1”, “12”, “31”, “23” and “6” node “7” precedes them in the hierarchy, so he is their indirect parent –**ancestor**, ant they are called his**descendants**. **Root**is called the**node without parent**. In our example this is node “7”.**Leaf**is a**node without child nodes**. In our example – “1”, “12”, “31”, “21”, “23” and “6”.**Internal nodes**are the nodes, which are**not leaf or root**(all nodes, which have parent and at least one child). Such nodes are “19” and “14.**External nodes**are the nodes, which have no child nodes i.e.**leaf**nodes.**Depth**of a node we will call the**length of the path from the root to certain node**. In our example “7” as root has depth zero, “19” has depth one and “23” – depth two.**Height**of a tree is equal to the**maximum level of any node in the tree**. The height of the tree in our example is “2”.**Level**of a node n is the**number of edges on the path from the root node**to n. In our example, the level of node “31” is two. By definition, the level of the root node is zero.**Degree**of node we call the**number of direct children**of the given node. The degree of “19” and “7” is three, but the degree of “14” is two. The leaves have degree zero.**Branching factor**is the**maximum of the degrees of all nodes**in the tree. In our example the maximum degree of the nodes is 3, so the branching factor is 3.

### Types of Trees

- Binary trees: A
**binary tree**is a tree data structure in which each node has at most two children, which are referred to as the*left*child and the*right*child - K-ary Trees: A
**k-ary tree**is a rooted tree in which each node has no more than*k*children. It is also sometimes known as a**k-way tree**, an**N-ary tree**, or an**M-ary tree**. A binary tree is the special case where*k=2*. - Red Black trees: A
**red**–**black tree**is a binary search**tree**in which each node is colored**red**or**black**such that the root is**black**. The children of a**red**node are**black**. Every path from the root to a 0-node or a 1-node has the same number of**black**nodes. - AVL Tree: It is a
**self-balancing binary search tree**. In an**AVL tree**, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property

### Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:

- Trees reflect structural relationships in the data
- Trees are used to represent hierarchies
- Trees provide an efficient insertion and searching
- Trees are very flexible data, allowing to move subtrees around with minimum effort