This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Breadth-first Traversal Solution" Lesson
>> Brian Holt: Hopefully this one was okay. Just people here in the room, who was able to solve it? Yeah, mostly, no one? Okay, okay, cool. Just kidding. [COUGH] We're gonna do iterative first in terms of solving breadth versus traversal. And then I will just go through and just quickly show you as well how to do recursive, if that's what you want to do.
>> Brian Holt: What we're gonna do here,
>> Brian Holt: The way this is gonna be passed into, if I remember correctly, is it's passed into with the root node already in the queue, right?
>> Brian Holt: So what we're gonna do here is we're gonna say, while queue has length, because as soon as it's empty, then it'll stop the why loop, because queue length will be zero, that which is false.
[00:02:02] It is what it is, it's what we got. So we will call shift, then what we're going to do is we're gonna say array.push(node.value). My friend here earlier asked, what order do we do this in and just to reiterate here? It doesn't actually matter which order that you're gonna do it in because you're just gonna go through another iteration eventually, it doesn't matter if you add the things first or not.
[00:02:30] So, does it make more sense now? Cool. She's not ME so I feel okay. [LAUGH] So, then we're gonna do, if there is a left node to process then we're gonna say, if (node.left), I can spell, queue.push(node.left), and then we will do the same for the right. So if (node.right) and queue.push(node.right).
[00:03:00] This order does matter. You have to do the left one first, right? But everything else does not matter, okay? And then you will just return the array.
>> Brian Holt: Now if you want to be a little bit more defensive here, which I was encouraged defensive driving and programming, you will say if queue or queue.length.
[00:03:35] If they don't give you a queue or something like that then you just wanna return array or something like that. But in this particular case I'm not really looking for edge cases but you'll see that in the completed part so I just felt like I should put it there for you.
[00:03:50] We should probably see if that works.
>> Brian Holt: And it works. So this is the iterative approach to doing breadth first traversal. This is the more efficient way, and I would argue not too unreadable, right? Pretty straightforward. Usually when you're trading off iterative versus recursive you're trading off for readability, and usually the recursive method is usually more readable.
[00:04:15] That's usually why you would select recursive or you have to take advantage of like recursive properties. In this particular case, it doesn't matter. I think this is good. This is the way that I would choose to write it. However, I did tell you that I would show you how to do recursive, which I have up here as well.
[00:04:34] So const recursiveBFT = (queue, array).
>> Brian Holt: So the first thing you want to do if (queue.length) then return array. So, if I pass you an empty queue then you just going to return array, right? It follows, it is our base case, right? Then here you're gonna say const node = queue.shift, and you say array.push(node.value).
>> Brian Holt: And then you're gonna say if (node.left) queue.push(node.left). node.left.
>> Brian Holt: If (node.right) queue.push(node.right) return recursive,
>> Brian Holt: queue.array.
>> Brian Holt: And that should work as well. Most loops can be rewritten recursively this way.
>> Brian Holt: In fact, I would probably argue this is even a little bit harder to read than this one because it's just a lot of cognitive overhead to picturing things in a recursive way.
>> Student: I'll go ahead and repeat the question I had asked during the break.
[00:07:03] And it does make more sense now seeing the code. But, sorry.
>> Brian Holt: You're okay.
>> Student: I asked if it's possible to get out of sync if you're doing breadth first traversal in a massive Search tree where it would end up processing a level deeper on the left than on the right, for example.
[00:07:45] And so if you write it like this, it should never get out of sync because you're always just putting things into the queue. And if you're always adding them to the queue in the same order and things like that, like, if I did like, math dot random in here a bunch of times then you can probably find a way to get out of sync.
[00:08:01] But no, it should work the same way every single time. Where you would run into problems, perhaps in other languages, if you're trying to concurrently process these things. But this is not the strategy that you would employ to process it concurrently, or rather, in parallel. That's more what I mean.
[00:08:15] Does that answer your question?
>> Student: Yes.
>> Brian Holt: Cool.