Depth-first, breadth-first searches
Week one of Fullstack complete! I am happy to report that so far, so good. Iâm sure that it would have been totally possible to learn these concepts on my own, but Iâm feeling pretty confident that personally Iâm learning things much, much more quickly with a group.
While the first week definitely had a lot of review, and a fair share of obligatory non-program related topics (games, norms, orientation, that sort of thing), Iâve also been introduced to several new topics this week that Iâm totally obsessed with right now, that I felt obligated to mention here, if only in a sort of cursory way.
My favorite a-ha this week was probably learning about breadth-first vs depth-first searching. Near the end of this week we tried to recreate (some of) the functionality of the $() selector function in jQuery. In doing so we created what I later learned was a recursive depth-first search function. While for most programmers Iâm sure the phrase ârecursive depth-first search functionâ does not seem all that surprising or interesting but as I reflect back I realize that itâs the kind of thing that would have felt super overwhelming to me last month (or even maybe last week). So letâs break it down.
First some (maybe overly obvious) context: websites have what is called the DOM. Which stands for the Document Object Model. The DOM is simply an organizational structure for what to go where on the page. For example how might you tell a computer to put all of your navigation buttons inside a navigation bar? I guess you could just stack each other, but wouldnât it be nice to instead have the navigation bar own or be the âparentâ of each individual button? You can! (and do!). This organizational structure is known as the DOM, and is basically a hierarchal tree. jQuery, a javascript library, allows you to add some nice functionality to your website (think drop-down menus, filters, and other fun things). And jQuery does this by traversing the DOM. Basically it goes through this hierarchal tree and gathers the right elements (maybe only the photos for example) and allows you to do cool stuff with it. We do this in our javascript file by writing something sort of like this:
 $(âstuffYouWantToSelectForGoesInHereâ).on(when you click on the selected thing){
      exactly what cool stuff will happen to the selected stuff
Ok, ok. So thatâs pretty nice. But how exactly does it do thisâŚtraversing stuff? How do we walk the DOM and determine âis this the right element?...nahâŚthe next oneâ? What order do you look for things? Does the order even matter?
In comes our recursive depth-first search. When recreating our $()selector, we made a function that basically does the following:
creates an array which will eventually store all the matching elements
decides that if we havenât given it an area to search, it takes in the Body of the DOM (the main part of the DOM that we are interested in)
determines if that particular section has any children
if it does, it waits to run this exact same function on those children, and then concatenates whatever is returned from those functions in our array.
then returns the newly filled array of matched items.
Recursion is a cool concept that feels very magical. Which may seem like reason alone to use this type of function. But just because itâs magical doesnât mean itâs the only way or the best way to solve this problem. This type of search is known as depth-first, which means that it goes down/deep into the DOM tree, then back up and to the right. For example letâs say youâre looking through your family tree to find all the family members that have red hair. With a depth first search you would first search through the eldest great grandmotherâs children, grand children, and great grandchildren before going to the great grandmotherâs younger brother. This I find hard to describe in words and easier to describe in pictures.
This differs from say a breadth-first search, which says letâs look at all the great grandparents first, then the grandparents, then the parents, then the children, then the great grandchildren, etc.
But why does it matter? Well in our particular case of recreating the jQuery selector it probably doesnât really matter that much, what order you find things in. But what if you were searching for something in all of the interwebs? Would you want to return all matches from one particular websiteâs childrenâs childrenâs children? Or would you want to just return the homepages for the most popular websites? Do you want to return your emails that ever mention the word Sarah? Or do you want to first return all emails that are from Sarah first, then have Sarah in the subject, and then have Sarah in the text? These are probably more analogies/metaphor than actual implementations of breadth first searches, but still I think it helps to put in context why weâre learning what weâre learning. Essentially if you need to return all of the matches then depth-first searches are fine, but if youâve got a huge number of potential matches and would like to return the top results first and continue searching in the background then a breadth-first search might be a better fit.
Well, I hope that was at least mildly interesting, understandable and accurate! I would welcome any feedback.Â