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
[00:00:00]
>> 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.
[00:00:28] So,
>> 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:01:10] It coerces to false anyway. Then what we're gonna do is we're gonna say const node = q.shift. This is always a weird one, shift. You might be familiar with push and pop, those are probably more common JavaScript operations. Push you add something to the beginning of the array, and pop you will remove something from the end of the array, right?
[00:01:38] Well, JavaScript also has something called shift and unshift, which are doing it from the beginning of the array. I think they are the worst names, but it's what we have. So shift will take something off the front of the array and return it to you, whereas unshift, which is literally the worst name I could think of, will add something to the beginning of the array.
[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).
[00:05:19] (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.
[00:06:21] So this is how you'd write it, but I would suggest that this is the superior way of writing it in both. Well, the performance profiles of these in another language would be about the same, because this is what's called a tail call, right? And you can do what's called tail call optimization, which technically should exist in JavaScript, but doesn't.
[00:06:41] That is a whole discussion for another day. You should definitely troll Kyle Simpson about it on Twitter, he loves that. [LAUGH] About what he thinks about tail call optimization in JavaScript. Nonetheless, it's tangential. So any questions about this before we move on?
>> 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:24]
>> Brian Holt: Well, the nice thing about JavaScript, that's a great question, by the way. The nice thing about JavaScript is it's single threaded. So you're not processing these in parallel at all, right? So if you wrote this, this is deterministic in the sense that it's always going to run the same way, no matter what.
[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.