## Data Structures: Trees

- Non-Linear data structure
- Hierarchical structure to increase search speed

## Definitions

Tree structure Definitions
collapse
Node relation Definitions
collapse
Tree Definitions
collapse

**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)

## Types of Trees

Types of Trees
Strictly Binary Tree
Extended Binary Tree
Full Binary Tree
Complete Binary Tree
Binary Search Tree
collapse

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.

collapseA 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

collapseA tree where each left subtree contains smaller values and each right subtree contains larger values.