## We did it!

We are done with lists...

but in a sense... the next data structure is a list with multiple paths...

The best part is that our knowledge of recursion will get very solidified over the next couple sections most traversals are recursive...

### All programming eventually leads to trees

I swear, every complex project I have ever worked on ends up being a tree exercise. I hope you are ready! This is where we really have to put all of our skills together.

### Welcome to day 2!!!

This is day two and we will be jumping right in!

### Also I am plaque licking close to YT

Less than 4k subs. So pumped

### For those just coming back after day 1

So for day one we covered everything to do with lists. We focused heartily on them. Today we will be focusing on more complex algorithms. We will be focusing on Trees/Graphs/Maps.

### Where are trees?

- Your filesystem is a tree
- The dom is a tree
- Trees are massively important in compilers. You have probably mininumly heard the term Abstract Syntax Tree.
- and there is more...

### Lets do a quick whiteboard example to solidify it.

Just in case none of those examples stuck with you

### Terminology

root - the most parent node. The First. Adam.

height - The longest path from the root to the most child node

binary tree - a tree in which has at most 2 children, at least 0 children

general tree - a tree with 0 or more children

binary search tree - a tree in which has a specific ordering to the nodes and at most 2 children

leaves - a node without children

balanced - A tree is *perfectly* balanced when any node's left and right children have the same height.

branching factor - the amount of children a tree has.

Hopefully this makes "seeing" quicksort start to make more sense... Its just a structure.

### Traversals

there are different ways in which you can visit the nodes of a tree.

- pre order
- in order
- post order (whiteboard)

### Lets code for a second

Lets create all three different traversals!

### These types of traversals are known as

Depth First Search. But that isn't the only traversal there is!

Breadth first search. (whiteboard)

### Lets implement

- bfs

### One Question

What do you like more?

- BFS?
- DFS?

### PRACTICE PROBLEM!

This use to be a very common problem in the hiring world.

- Comparing two binary trees to see if they are equal in both shape and structure.

Lets first whiteboard it (whiteboard)

### Questions before we implement it?

(to the greatest editor)