# Introduction to Trees

Trees are another data structure we often encounter. They're useful for manipulating hierarchical data, sorting and searching.

# Definitions

- Edge
- Connections between nodes.
- Path
- Connected edges (ways of following lines to get between nodes).
- Height
- Length of longest path from root (i.e. how many levels down the lowest leaf node is).
- Node Level
- Length of path from node to root.
- Balanced
- Tree has the minimal possible height for the number of nodes, and the number of nodes in the left and right subtrees differ by 0 or 1.
- Degenerate
- Tree with maximal height for the number of nodes (e.g. basically a list)
- Descendants
- All nodes below the current node, reachable by a path.
- Internal Node
- A node with children.
- External Node
- A leaf node, no children.

# Types of Trees

## Ordered Tree

An ordered tree is, as the name suggests, a tree where the data is ordered based on something such as size.

## Binary Tree

A binary tree is a tree where each internal node (non-leaf node) has at most 2 children.

### Full Binary Tree

In a full binary tree every internal node has **exactly** two children

### Perfect Binary Tree

In a perfect binary tree all leaves are at the same depth. Meaning that each leaf is the same number of levels down from the root as every other leaf.

### Ordered Binary Tree

Essentially a combination of an ordered tree and a binary tree.

The left children <= parent, and the right children >= parent.

It's also called a binary search tree.

### Full m-ary Tree

Each internal node has exactly m children.

# Binary Search Trees

As said above, a binary search tree is an ordered binary tree. More info

# Tree Traversal

There are a number of ways to traverse a tree; depth-first and breadth-first being one way of splitting the two types.