Trees are a subset of graphs, a non-linear data structure, that provides an efficient way for searching and sorting. They are a collection of nodes and are a way to store information hierarchically.

Similar to regular trees, they have parent and child nodes that are connected in a hierarchical fashion.

A binary tree is a tree data structure in which each node has at most two child nodes, known as the left child and the right child. The topmost node in the tree is known as the root, and each child node can have its own subtrees, which are also binary trees.

In a binary tree, each node has a unique value, and the values in the left subtree of a node are less than the value of the node, while the values in the right subtree are greater than the value of the node. This ordering property makes binary trees useful for searching and sorting data.

In this example, the node labeled 1 is the root node, while 8,9,10,11,13, and 14 are the called leaves, and the rest of the nodes are called internal nodes.

Some terminology:

- Size - number of nodes in the tree
- Lengths - number of edges in a path
- Depth - length from the root to a given node

**Full tree** - tree where every node have two children except the leaves

**Complete tree** - every node has at least two children except for the bottom level, and they have to be filled in as far left as possible

**Degenerate tree **- every node only has one child node

**Perfect tree **- every internal node has two children and all leaves are on the same level

**Balanced tree** - height of the left and right subtree of any node differ by not more than 1

For traversal of a binary tree, there are three different ways:

- pre order: current - left - right
- in order: left - current - right
- post order: left - right - current

preorder: [1,2,4,6,3,5,7,8,9]

inorder: [6,4,2,1,3,7,5,9,8]

postorder: [6,4,2,7,9,8,5,3,1]

Breadth first traversal, an alternate to depth first, is an algorithm that searches each level, left to right.

- Add to the top left most spot
- Breadth first traversal - find the first open available spot while the you haven’t reached the size of the tree

Algorithm Steps

- Add root node to a queue
- Check node in the queue if they have a left child
- If not add the new node to the tree in that spot
- If there is a left child check if it has a right child of the node
- If not, add the new node to the tree in that spot
- Add the children of the node to the queue
- Check each node in the queue, they will be in a level order, repeating previous steps

- Remove item
- Replace with the item at the bottom right most spot