Day 82 Searching Algorithms & Data Structures
Day 82 is in the books! Today we were introduced to depth and breadth-first search. These are methods of searching either graph or tree data structures. Let’s take a look at the biggest difference between these two algorithms.
On the left you have an illustration that represents depth-first search. Depth-first search traverses down through all of the nodes on the first branch before working it’s way back up and moving on to the next child of the root node. It works its way through nodes in a vertical fashion.
On the right you an illustration that represents breadth-first search. Breadth-first search traverses all of the siblings nodes on each level before moving down and searching their descendants. It works its way through nodes in a horizontal fashion.
How you select which algorithm to use depends greatly on the tree/graph structure that you are working with. It you have an idea of where your solution might be that can also affect your choice of algorithm.
The second half of the day today was spent working on some data structure exercises. One of the assignments was to convert a tree data structure represented as an array into a tree of nodes. The array I needed to convert is shown below:
That’s a little bit hard to understand so I’ve included a simplified representation of the tree below:
The example above is pretty much what our tree of nodes will look like once it’s been converted.
In order to make this process a little bit easier we’re going to need a constructor that will create a new node for us. We will also need a helper method that will add child nodes to a parent node. Examples of both can be found below:
Below is the final implementation. I’ve added some comments for clarity.
Look at all of those beautiful passing tests! That’s a coders dream right there.
Tomorrow we are working hard to finish up all of our assignments before we get started on our capstone projects. We do have one more week of lectures next week, but there will be no more assignments required apart from our capstone project. Next week we get to learn graph data structures which should be really fun. I’ll keep you guys posted on how things are progressing as always. Until next time…happy coding.
82 down 18 to go