### What are trees?

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.

### What are binary trees?

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

### What are the different types of binary trees?

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

#### How do you traverse a binary tree?

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
##### Practice

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.

#### Insertion in level order

• 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

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

#### Deletion in level order

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