# Binary Trees

## Prerequisites

### Binary Trees

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