#### Introduction

- Trees are structures that represent hierarchical data.
- They are formed of nodes connected together in parent-child relationships.
- There is a special node, called the root, which has no parent.
- Each child node may have its own children.

#### Example

#### Terminology

- Root:
- The foor tis first node in the tree. In the above diagram 'Colors' is the root node.

- Internal / Branch node:
- Any node which has children is called an internal or 'branch' node.

- Leaf:
- Any node which doesn't have children.
- The plural of leaf is 'leafs'.

- Child & Parent:
- Any node that has child nodes becomes the parent to those nodes.
- Leaf nodes are never parents.
- In the above diagram, 'Blue' is a parent while 'Dark Blue' and 'Light Blue' are its children.

- Siblings:
- If two children have the same parent then they are siblings.

- Descendant & Ancestor:
- The descendant / ancestor relationship is similar to that of child and parent, except that the descendant doesn't need to be an immediate child of the ancestor.
- 'Dark Blue' is a descendant of 'Colors'.

- Breadth:
- The number of leaf nodes.

- Height:
- The height of a tree is the length of the longest path between the root node and a leaf node.
- In the example above, this would be 2.

- Size:
- The total number of nodes in the tree.

- Degree:
- The degree of a node is the number of children it has.
- Leaf nodes have a degree of 0.
- The degree of a tree is the largest degree of any of its nodes.
- In the above image, the degree of the tree is 3.

- Level:
- The distance from a node to the root.
- The root is at level 0.
- It's children are at level 1.
- Their children are at level 2.
- and so on.

- The level can also be defined as a set of all nodes at the same level.

- The distance from a node to the root.
- Forest:
- An ordered set of trees.

#### Rooted vs unrooted trees

- When we refer to a tree, we are referring to a rooted tree.
- However unrooted, (aka free) trees also exist.
- the only constraint on an unrooted tree is that there exists a single unique path between any two nodes.

#### Ordered vs unordered trees

- Ordered trees:
- The children of an ordered tree have a specific order.
- In the above image:
- The trees are not considered equal.
- This is because the children of the 'a' node are in different orders.

- If a tree is ordered then we can refer to a specific child by its index, e.g. the first child of 'a'.
- Ordered trees are the default. When someone refers to a 'tree' assume they are referring to an ordered tree.

- Unordered (aka oriented) trees:
- The children of an unordered tree do not have a specific order.
- In the above image:
- The trees are considered equal.
- The order of the children is not important when determining equality.

- It is not possible to refer to a child by index.

#### K-ary trees

- A k-ary tree (aka m-ary tree) is a tree in which each node has at most 'k' children.
- A binary tree is a k-ary tree with
`k = 2`. Each node has at most two children: - A ternary tree is a k-ary tree with
`k=3`. - K-ary trees differ are not proper trees:
- K-ary trees can be completely empty, while trees must have at least one node.
- K-ary trees can have empty nodes:
- In the image above, the 'b' node has no left child. I.e. its first child is empty.

#### Code (Python)

```
# -*- coding: utf-8 -*-
class Node:
def __init__(self, data):
self.children = []
self.data = data
def addNode(self, node):
node = node if isinstance(node, Node) else Node(node)
self.children.append(node)
node.parent = self
return self # returns self so addNode() can be chained
def __str__(self, path = '', last = True):
ret = path + ('' if not path else ('└─ ' if last else '├─ ')) + self.data + '\n'
for child in self.children:
ret += child.__str__(path + (' ' if last else '│ '), child == self.children[-1])
return ret
```

##### Usage:

```
tree = \
Node("Colors") \
.addNode(Node("Blue")
.addNode('Light Blue')
.addNode("Dark Blue")) \
.addNode(Node("Red")
.addNode("Light Red")
.addNode("Dark Red")) \
.addNode(Node("Green")
.addNode("Light Green")
.addNode("Dark Green"))
print(tree)
```

##### Output:

```
Colors
├─ Blue
│ ├─ Light Blue
│ └─ Dark Blue
├─ Red
│ ├─ Light Red
│ └─ Dark Red
└─ Green
├─ Light Green
└─ Dark Green
```

#### Time Complexity

- Trees are often more efficient than simpler data structures such as arrays and lists.
- if an operation takes linear time on a list (such as searching) then it will usually take logarithmic time on a tree.
- Assuming the tree is well organized.