Crack the Code: Breadth vs Depth First C# Iteration Explained

if you've been finding breadth first versus depth first Concepts really confusing in computer science I wanted to make this video to help you out hi my name is Nick centino and I'm a principal software engineering manager at Microsoft in this video I'm going to go through a c example where we tried traversing a file folder hierarchy and I really like taking really practical approaches of this kind of stuff because for me personally that was one of the best ways that I could learn as soon as these things start getting more mathematical and more theoretical they were seemingly simple and they got really convoluted very fast but taking something Hands-On very practical really made it solidified for me if that sounds interesting just a reminder to subscribe to the channel and check out that pin comment for my courses on dome train with that said let's go over to visual studio and check out this example on my screen right now I have an example of a depth first iteration approach to going through a file folder hierarchy now when we think about this the variations that we have are going to be a depth first approach versus breadth first when we think about depth first we want to go deeper before we start going wider and of course bread first is going to be the exact opposite I think when we go to print out the results of these things it should make it much more obvious in terms of how they're functioning and that's exactly why I like to use sort of what seems like a more practical example to doing things now we're going to start with the depth first approach here and then what we're going to do after is look at the breadth first approach and we're going to compare because they're almost identical but we're going to be swapping out a data structure to make these things work so let's start by checking out the algorithm you can see that I have this class declared here starting at line five and it just has a run method inside of it which is going to take a root directory for us to look at so on my hard drive I just have a folder that has some coar material in it from Dome train that I've created and what we're going to do is start off by checking to make sure that we're not dealing with an empty directory so just sort of an edge case to look for at the beginning and from there what we're going to do is start by putting our top level folder so this root folder we're looking at we are going to push that onto a stack and I've declared that stack right here on line 15 and if we look closer at line 16 I've also created my own data structure here to hold a record and I'm just going to explain this very briefly what I'm doing is I'm taking the sort of the path that we're dealing with actually it's probably easier if I just jump down to it down here but if we look at entry I take the path so this is the full path we're dealing with then I'm also just storing the name for Simplicity and then I'm going to store the level and when we think about the level this is sort of just how many folders were deep inside of our sech so if I scroll all the way back up here the idea is that if we're starting at the root we are zero levels deep you don't need to track the level it's just that when I go print this stuff out to the console I wanted to make it very obvious visually how deep we are so that's just why I'm using it that way now the idea here is that we're going to be looping through our stack full of these entries which are going to represent the different folders that we have and we want want to keep looping until we're done so once that folder collection so the stack in this case once that's completely emptied out we've done and we finished traversing everything the way that we start making progress through our stack that we're dealing with here is that we need to pop off the top level of that collection of folders and the first time through this we've only put the root onto this stack so if you visualize it we have our empty stack we've now put the root on top of it and now we're popping that off so we've just put something on and taking it right back off but that's because it's just kicking off our algorithm That We're looping through so we've now taken that thing back off the top and we're now looking at the entry that's representing the root folder this is just going to calculate a basically empty string the first time through because the level is zero so if we have zero spaces which is what this is saying it's just going to be an empty string the first time through so that means when we go to right out to the console this is going to be empty because there is no indent followed by the name of the folder so we should see in this case if I scroll back up the first thing we should see is courses printed out into the console from there what we're going to do is we're going to ask for all of the files at that current depth of our search if there are no files basically this call right here on line 25 will return no items if there are some we will be able to iterate through them and print out all of the file names with the indentation right in front and you'll notice I've calculated the indentation again right above so it's one level deeper than the folder depth that way of course if we're printing out all of the files they look like they're indented inside of the folder Just For A visual representation hopefully so far pretty straightforward so again if there are no files this will basically do no work because it's empty and if there our files just in that current level that we're looking at we'll print those out from there though what we're going to do is we're going to ask that directory not for the files now but for the other folders that we have within it again just at that top level or the current level that we're at so if there are any folders then we're going to make a new entry and we'll add one to the level that we're currently at this way it seems like the folder is one level deeper when we go to print it out and then from there we're going to push that entry onto our stack and keep in mind that when we're thinking about a stack data structure every time you add something or you push it onto the stack it now goes to the top of the stack so every single time you add one more thing onto the top and every time you pop something off of the stack you start removing it from the top a q which we'll see later works the exact opposite way so a stack is what we're currently using and hopefully if that makes sense visually when you're adding things on they stack on top and when you remove them they pop off of the top Just A visual representation as we're going through this that means that as we're adding things onto here basically the first folder that we come across will get added onto the stack and if there's another folder we will go put that on top of the stack so just again try to have this visualization and as you're going through this exercise and you take this code and you try it out for yourself I would highly recommend you get a pen and paper and try drawing it out because this kind of thing if it's not really registering and clicking with you I would say having pen and paper and trying to go through the code and draw out what each iteration of the loop is doing I think personally it makes a tremendous difference in trying to solidify your understanding let's continue on and see what happens once we go back up to the top of the loop before we continue on this is just a quick reminder that I do have courses available on dome train if you're just getting started in your programming journey and you want to learn C you can head over to D train I have a getting started in C course it's approximately 5 hours of content taking you from absolutely no experience to being able to program in C and after that I have my deep dive course which will take you to the next level with another 6 hours of content so that you can start building basic applications head over to D prane and check it out let's head back to the video so we would check to see okay is our collections or our stack in this case does it still have anything inside of it and if we happen to have folders from the previous iteration all of those folders will now get added into the stack so we will check and say hey look yep there was at Le at least something added and then we're going to go ahead and pop it off from here we just repeat this entire process and what should be happening is every time we come across files at a particular folder level we'll print them all out and that's what this Loop is doing right here so this part that I'm highlighting is responsible for always printing out the files in the folder this part here that I'm highlighting from line 21 to 22 is responsible for always printing out the current folder and then this part that I'm highlighting down here is responsible for basically getting ready the next set of folders that are in our current directory so each part of this code has a particular purpose again what I'm highlighting here gets the next set of directories what I'm highlighting here is going to print all the files of the current directory and what I'm highlighting here from line 21 to 22 is just printing out the name of the directory that we're currently at and to wrap it all up this while loop so the online 18 that's checking the condition as well as the pop part on line 20 so folders. poop these two things together allow us to basically keep iterating and popping off the next iteration that we have to go looking at if we scroll back up to the top you can see that I currently have this one all set up like I said it's pointing at a folder that I have with some chorus information I'm going to go ahead and run this it's super quick so if I press play we'll see it pop up and now that it's finished again very quick I'm going to move it over on one part of my screen scroll all the way to the top there's a lot of stuff in here it's just a lot of compiled code and some garbage so I'm going to pull up my file folder Explorer and we're going to see if we can go through them together unfortunately on the right hand side when we're looking at the file folder structure I'm unable to zoom in effectively so if there is some text it's a little bit hard to read hopefully my editor can zoom in for us a little bit but we should be roughly okay to go so at the top level you can see that I'm starting in the chuses folder so that's what we see up at the top and in my bar rate at the top here you can see that it says courses from there Dome train is the next folder we see right so if I go in there's Dome train if I go in one more there's reflection which is what we see here and now this is the first time that we're going to see sort of a a deviation because we see code and videos here but just videos here and if we think about what's going on here so I didn't prove it and I didn't explain it but we're asking for the files and folders it's up to the the file system in this case to give us back the files and folders in whatever order it wants to give us those back I didn't ask specifically for them to be in alphabetical order but we might assume in this case that it did give them back to us in alphabetical order and if we think about that stack remember so if it gave us code it's going to put code onto the stack and then it gives us videos we're going to put videos onto the stack the next time we go through that iteration what's at the the top of the stack videos If we have a look on the left hand side that's exactly what we popped off of the stack so if I go into videos we're going to have this same pattern again right so you see edited and raw but what do we have on the left hand side just raw and it's the same reason because we're going to keep going deeper so I'm going to go into raw and then I have 9.0 so it's going to go into here if you think about this one it's a little confusing because if it was alphabetical you might say well why the heck did it Pick N instead of 11 here and it's because 11 is a bigger number but alphabetically 9 is greater than one so that's why it's going to nine right so let's do that and then 9.2 same idea here and finally we're going to get into this folder okay so that's that and then what's going to happen is we're going to say great we've reached the end here there's no more folders makes sense we'll go back out and what was the other one that we had queued up onto the stack well we popped off 9.2 but 9.1 is now the next thing on the stack which is why if we go into here and we see it on the left now we get these two videos which are on my screen but at this point there's no more folders in here that it queued up if I go back up to this level there's also no more folders that it would have added onto the stack from here so it has to go back up one more now and again thinking about the order that it would have placed these onto the stack this is probably a lot more obvious if you're stepping through the debugger and looking at it as it's adding the things onto the stack but I wanted to show you the visual representation practically I didn't want to go draw like a funny tree structure and stuff I wanted to show you Hands-On what this file folder structure looks like but you can see that 7.0 is the next one and if I scroll a little bit more it's very much like what we just saw with the 9.0 folder but this time there are three folders inside of here and that's why you see these ones printed out hopefully so far that's making sense and that's going to be how we do a depth first iteration approach to file folder hierarchies I'm going to go ahead and stop this and we're going to swap it out for the bread first approach so I have this other implementation what I'm going to do is keep this one expanded I'm just going to jump down to this code here now I don't have them side by side but I just want to call out unless you have super vision and super good memory that these are almost the exact same in terms of code setup but there's one fundamental difference and I hinted at it earlier it's going to start here on line 52 and that's because we're not using a stack anymore instead of a stack we're going to use a q this is because the Q data structure works basically backwards from the stack with the stack we were adding things onto the top and then we were removing things off of the stack when we're queuing them up we're going to be taking them out in the order that we were putting them in so the exact opposite of a stack as I just mentioned but that means we use the inq method and you can see that on line 53 and 73 and then DQ so instead of push and pop it's inq and DQ otherwise this code is the exact same and that means that we can basically take this exact same algorithm I don't necessarily have to walk you through it in terms of this code here but if we keep in mind that what's going to be happening is that and queuing and deqing works in the opposite order from push and pop that means that we're going to be traversing things in a different order let's go ahead and run this one now I'm going to press play and already it looks a little bit different but let me scroll up to the top here if you remember what we were just looking at and if you don't feel free rewind the video go back have a look at it right I don't expect that this is necessarily going to be something that you know sticks out in your mind perfectly and uh don't think that's normal for anyone so don't worry about it but if I go all the way back to the Dome train folder right now so I'll go to corses actually courses is at the top in both of these cases right going into courses we have one single folder it's Dome train and the same with reflection so so far so good but what's different about this one now well it's going to go into code next now I don't want you to hyperfocus on the fact that it went into code instead of video necessarily because maybe the the sord order is different whatever it happens to be that's not really the important part but what is important is that it's going to go into code right and what it did was once it's in code if we scroll down a little bit what it did was it went to print out get ignore and reflection right the solution file but look at all these folders in here Why didn't it go print those out kind of interesting well it's because it's doing a breadth first approach so it's said I need to go into this code folder and print out the files and then what I'm going to do is I'm going to add all of these folders onto the queue the stack was adding them as the next thing that it needs to pop off but with the Q they go onto the basically the end of the que they have to go wait their turn in the order that they were put in these ones weren't added before if I go back up they weren't added before the videos one the videos folder is the next folder we have to go do but if we think about it all of these folders that I'm highlighting here came after videos so keep that in mind as I go back up so now we're going into videos which is what we see here notice there are no folders inside of the video print out if I jump into here you'll see right there's no folders that it's printing out in fact there's no files very interesting right well where the heck are these coming from where is this dogit coming from so let me go back and go into code well here's G it might be kind of hard to see on this left uh on this left side here but dogit is interesting because it might look like it's a file but technically it's this folder and it's really hard to see but that dot is actually the character position sort of indented one level before commit message so that means we went into here we went into the dogit folder and then you'll notice it printed out all of the files so I'm going to highlight on the left here as well these files are the same sorry I missed one cuz that vs folder is misleading but these are the six files that it has printed out on the left and again it did not print out the folders right away in my opinion it's really confusing to read the left hand side because you might expect that you see the folders at the same level but every time it finds a folder it goes and adds it to the queue again that folder has to wait its turn to be the next folder to come off of the queue hopefully you can see that this p pattern still continues and if I go back up because now we've printed all all the files we've added all of these folders onto the queue well the next thing on the Queue would be this vs folder and how many files do we have in here zero but how many folders do we have to get added to the queue but that's why vs again kind of hard to read here sorry because the dots small but there's no files printed out underneath vs cuz there simply aren't any here at this Point what I figured I would do is because we've already walked through some of the output and we've seen that we can compare both breadth and depth first I was just going to go ahead and put a break point inside of this part here in this while loop and maybe I'll actually put it right after we DQ things and then I was going to put uh maybe I'll just run it and we can set another break point as it makes sense but I wanted to show you what's happening as it goes through from the code perspective okay so starting things off in this approach here we're going to look at the first folder that's coming off of the queue and that's going to be the root that we put in which is the courses folder that we're starting with so that's the first one that we see and I just wanted to show you as we start walking through again calculating the indentation this is just kind of to print out the console doesn't really matter but how many files did we have in the chorus's folder there should be none so if I step over this you'll see it jumped over the loop because there simply are no files but there are folders and there's only one so we should go into here that directory we see is the Dome train folder inside of the ch's folder so it's going to go add it onto the queue and that's it the first pass through here it's really not that exciting right didn't find any files the folders collection this Quee we already emptied it and then we added one more thing so the next time through it's basically the exact same thing except we're one level deeper in the items are tracking so if I pull out current folder it's now that Dome train folder and if we have a close look it says level one instead of level zero but it's G to look basically the exact same aside from how far it's printing in the console how many files are in that folder there's zero it's going to skip over this part again right and how many folders in here there's one so it's going to look the exact same in terms of the flow that we just saw so let's go ahead and add that this is now the reflection folder okay the next time through what's it going to look like probably pretty similar so it's kind of boring at the beginning but we're going to pull off the current folder we're now at level two we're looking at the reflection folder stepping through a little bit how many files are in there let's find out none so far we haven't even gone into that block of code to go print out the files there simply aren't any and that Q we've been emptying it every time we add something back on but let's see how many folders are inside of the reflection folder so if we go in one we have here is going to be called code so we're going to add that and it looks like now there's two folders so this is where it starts to become a little bit more interesting right we've now added code and now this new one here is videos before we move on to the next iteration if we look at our folders collection here there are two entries we'll see code is at position zero and videos is at position position one and we have to think that this is not like a stack whatever was added in first is going to be the thing that comes out first okay so they come out in the order that they were put in which means if I go to the next iteration here we go to DQ we end up getting the code folder so again if we check the folders collection there's only one thing and of course it's still the videos folder that's left over there let's step through now so how many files are in in this code folder it looks like we found our first file okay so we'll step through this file is called theg ignore file so I'll write that out looks like there's another file we'll go print that out that's a solution file print that out so there's two files that we added in and notice that when we do this we are not printing the directories as we find them right because this Loop that finds the directories is not writing them out every time we do an iteration of the loop and starting from this outside part right every time we enter an iteration that's the thing responsible for printing the directory that we're at so how many folders are in this one we end up having dog. vs okay so there's a bunch of folders in here now we have a 10.0 and if I keep going there's a whole bunch okay so I'm going to press F5 I guess before I do that a little quiz for you is can you recall maybe you need to rewind it's okay I just added a bunch of folders in here was this folders collection empty before we started doing that and the answer is no but which one is it and turns out you can probably see it if you're looking closely on the screen before I over it over it but it's going to be that videos folder the code folder that we were just in we queued up a whole bunch of other folders and if I hover over it we added 20 there's 20 folders that got added into here and we just pulled off the videos one that means once we finished this videos folder however many things it's going to add here we won't even get to them until we get through all 20 folders that are currently in the queue hopefully you can see how that pattern makes sense because I think that sometimes when people think about this traversal approach that sometimes the depth first approach makes a little bit more sense because you're kind of seeing things in a an order that you might expect a little bit more however if you are curious I do highly recommend that you try an algorithm like this so you can see the difference if you want you can check out this code however it's probably just as easy if you try thinking through it on paper and seeing you know which ones you should be printing first you could even ask an llm to try drafting some pseudo code for you I would recommend that if you're going to ask an llm for any help that you don't just copy the code blindly but I think if you ask it to code up some of the structure or even if you do get it to do the code for you make sure that you're asking it questions to understand why because the whole point that you're probably watching this video video is that you wanted to understand it a little bit better what's the point of doing that if you're not actually going to try and understand it because if you just needed the code you could have asked an llm or taken it from stack Overflow or something if you're trying to understand things you do need to take the time to try them out and walk through them if that means taking a pen and paper or stepping through the debugger a whole bunch or both please do that because it will help solidify your understanding in this video we got to see two different approaches to iterating over file folder hierarchies and we started off by looking at depth first and then I went into sort of a visual representation you could truly see the folders and files on my disc and then we did the same thing with the bread first approach in the end we only went and debugged the bread first approach so you could see what it looks like as we're stepping through different iterations in the debugger but of course I do recommend that if you want to see the depth first one try it out for yourself and see if you can follow along just like we did with the breath first part however this is all interesting because it's all about iteration but something that comes up all of the time in software development in computer science in particular is we end up seeing recursion and file folder hierarchies can be traversed with recursion so if you're interested in seeing how that works you can check out this video next when it's uploaded thanks and I'll see you next time