Trees

What is a Tree

A tree is a connected, undirected graph with no cycles in it.

Connected

All nodes must be connected to other nodes so that no part of the graph is separated. An unconnected graph is essentially 2 separate graphs.

Undirected

A tree can't have any directed edges/arcs. This will be an arrow on the edge/arc to indicate the direction of travel.

No Cycles

A run of interconnected nodes that return to the point of origin.

What is a Rooted Tree

A tree with one vertex singled out as a starting point.

What is a Binary Tree

A binary tree is a graph with no cycles in which each node is succeeded by a maximum of 2 nodes, a 'left' child and a 'right' child, therefore they can be either directed or undirected.

What is a Binary Tree Search

A binary tree can be created from a list of data:

1. The first item in the list will be the root of your tree.

1. You will then add an item to the tree by firstly comparing the new item to the root.
   1. If it is alphabetically Lower than the root the new item will be placed on the left of the root.
   2. If it is alphabetically Higher than the root the new item will be place to the right of the root.

1. The next item in the list will again be compared to the root.
   1. If it is alphabetically Lower than the root the new item will be placed on the left of the root. If the root already has a node to the left, the new item will be compared to this node as well.
   2. If it is alphabetically Higher than the root the new item will be place to the right of the root. If the root already has a node to the Right, the new item will be compared to this node as well.