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)