#### Introduction

- A binary tree is a type of tree in which each node has at most two child branches.
- These child branches are labelled left and right.

#### Example

#### Internal and External Nodes

- Internal nodes:
- An internal node is a node that has children.
- In the example below there are 4 internal nodes.
- The internal path length is the sum of the levels of all the internal nodes.
- In the example below the internal path length is: 1 + 1 + 2 = 4.

- External nodes:
- An external node is a node that does not have children.
- It is also called a leaf node.
- In the example below there are 4 external nodes.
- The external path length is the sum of hte levels of all the external nodes.
- In the example below the external path length is: 2 + 2 + 3 + 3 = 10.

- Example:
- The internal nodes are colored red.
- The external nodes are colored blue.

#### Full Binary Tree

- A full binary tree is a type of binary tree in which each node has exactly 0 or 2 child branches.
- They are also called proper binary trees or plane binary trees.
- Example:

#### Extended Binary Tree

- An extended binary tree is a type of full tree
- It is created by extending nodes of an existing tree:
- If the existing node has no children then two child nodes are added
- If the existing node has 1 child then a second child is added

- Example:
- The existing nodes are drawn as blue circles
- The new, extended nodes are drawn as red rectangles

#### Complete Binary Tree

- A complete tree is a type of binary tree in which every node as two children apart from the bottom level, which is filled from left to right.
- Example:
- Complete binary trees are useful because they offer the best ratio between the height and the number of nodes.

#### Perfect Binary Tree

- A binary tree is perfect if all of the external nodes are on the same level.
- Example:

#### Skewed Binary Tree

- A skewed binary tree is a tree which is dominated by either left or right nodes.
- Example:

#### Code (Python)

```
# -*- coding: utf-8 -*-
class Node:
def __init__(self, data):
self.data = data
def addLeft(self, node):
node = node if isinstance(node, Node) else Node(node)
self.left = node
node.parent = self
return self # returns self so it can be chained
def addRight(self, node):
node = node if isinstance(node, Node) else Node(node)
self.right = node
node.parent = self
return self
def __str__(self, path = '', last = True):
ret = path + ('' if not path else ('└─ ' if last else '├─ ')) + self.data + '\n'
if hasattr(self, 'left'):
ret += self.left.__str__(path + (' ' if last else '│ '), False)
elif hasattr(self, 'right'):
#we use a fake node for spacing
ret += Node("").__str__(path + (' ' if last else '│ '), False)
if hasattr(self, 'right'):
ret += self.right.__str__(path + (' ' if last else '│ '), True)
elif hasattr(self, 'left'):
ret += Node("").__str__(path + (' ' if last else '│ '), True)
return ret
```

##### Usage:

```
tree = \
Node("Colors") \
.addLeft(Node("Blue")
.addRight("Dark Blue")) \
.addRight(Node("Red")
.addLeft("Light Red")
.addRight("Dark Red")) \
print(tree)
```

##### Output:

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