• Non-Linear data structure
• Hierarchical structure to increase search speed
• Forest: A set of trees which are not connected to each other
• Tree: Nodes connected to each other in a hierarchical structure
• Sub-tree: A section of the tree below a certain node
• Nodes: Elements of the tree
• Edge: Lines connecting nodes - total edges in the tree equal the number of nodes minus 1 (removes the parent because it does not have a parent)
• Root node: The starting node and the only node without a parent
• Leaf node: Any node which does not have any children • Parent Node: The node directly above the current node
• Grand Parent Node: the node directly above the parent node
• Ancestor node: Any predecessor of the current node
• Child node: A node directly below the current node
• Grand Child node: A node directly below a child node
• Siblings: Two or more node which have the same parent
• Descendent Node: Any node connect in the tree below the current node • Level: The amount of hops from the root node ie number of edges eg root = level 0, child of root = level 1, grand child of root = level 2
• Height: Number of levels eg level 0,1,2 means there is a height of 3
• Path: A sequence of nodes where each node is a child of the previous. Any node can only have one path to it. eg root, child 1, grand-child 1
• Path length: The number of edges in a path
• Degree: The number of direct children eg the degree of the root node is 4 if it has 4 children (regardless of decendent nodes) A tree where each node has a maximum of two child nodes.    A Tree where each node has either 0 children or 2 children.  With n leaf nodes the tree has:

• n-1 binary nodes
• 2n-1 total nodes

Example: 4 leaf nodes means there are (4-1) 3 binary nodes and (2n-1) 7 nodes in total.

A Tree where each node has given special nodes if they do not have exactly two children. • Internal nodes: The real nodes
• External nodes: The added special nodes
• Internal path length: Sum of the path lengths of all internal nodes.
• External path length: Sum of the path lengths of all external nodes.

external path length = internal path length + 2 x totalNodes

E = I + 2n

A tree where each level has its maximum number of nodes.  A tree where each level has its maximum number of nodes except possibly the last level. A tree where each left subtree contains smaller values and each right subtree contains larger values. 