# Trees

### Trees

#### 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.

#### 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'.
• 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.
• 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

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") \

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.