Implement Breadth-First Search

[00:00:00]
>> Yeah, let's implement it, whoo! We're gonna do this. All right, so go back in here. And it's BTBFS, right? Binary tree, breadth first search. I know it's just the best, I love acronyms. So the thing about a breadth first search is we don't need to use recursion, right?

[00:00:15]
Right? This is not a Padme meme, we actually don't need to use it. We can just do this. So I'm gonna go like this, const q equals this. We're gonna pretend it's a q. It's not a JavaScript array list, we're actually gonna be using a q in this case.

[00:00:28]
And then we'll do this simple little operation of while (q.length), right? While the length is some sort of number other than 0, which luckily length can't be negative 1, or else we could be stuck in this weird version of purgatory forever. And we're gonna put the head inside of our q.

[00:00:44]
So now we have a q of binary node. And in this case, we're doing a breadth first search, not just simply a breadth first traversal. We're looking to see, does this number exist within this tree? And if it does, we will return true. If it doesn't, we will return false.

[00:00:59]
And we're doing a breadth first search. So let's do that right now. All right, so what's the first operation of doing this? Well, we haven't written out the pseudocode, have we? So it's gonna look a lot like depth first search, except for instead of recursing or recursing, we're going to push into a q.

[00:01:18]
So we'll do something like this, while q.notEmpty. By the way, don't actually name a function notEmpty, that is just a very silly function name. Cuz you put the negative in there, you should just say empty than not. Okay, anyways, so we're gonna have next = q.deque(), look at that.

[00:01:42]
So we get the next item out of the q. And then we could console log if you wanted to do something like that, but we're not gonna do that. Then we need to q.put, or not push, enqueue in next, I should have used smaller words. Next left, and then you can imagine next right, right?

[00:02:04]
That's pretty much it, right? That's pretty much all we're doing for breadth first search. We get the item, we could do an operation, we push in its children, or enqueue its children. So that makes sense? Hopefully that makes sense. So let's just do that right now. So we const, we can call current, or it actually doesn't really matter, q.unshift, no, shift.

[00:02:29]
There we go, q.shift, awesome. So we're gonna shift that thing on. And then, we need to do something else, right? We need to actually do the check, because we're doing a search, not just simply a traversal, right? Since we're doing a search, we're gonna go like this, if (curr?.value =, why are you doing this?

[00:02:47]
Yeah, I forgot you have to, TypeScript, you gotta do this thing on it, just because. If value equals needle, we can return true. Now, remember I don't like to return from a loop. But we're doing algorithms, we don't really care about the sweetest engineering right now. So we did our little operation to see, do we need to leave the loop?

[00:03:09]
Did we find the value we want? Else we need to keep on traversing, which is gonna be a breadth first one. So we're gonna push on to the end, right? Cuz a q, we removed from the front, we push on to the end. So we can kind of simulate a q via JavaScript here.

[00:03:24]
So curr.left, and of course, curr.right. And we need to do a check here, right? Because we have our q, we're not having a base case here. So we need to put our base case at the pushing step if we wanna do it this way. So if (curr.left), then we push in left.

[00:03:45]
If (curr.right), we push in right, right? So this is kind of simulating. This is where the iterative approach often becomes not as good. We could have had it so that we actually do a test here, right? Technically, it would be undefined or null, right? Cuz that's the interface of the q, and then we could do a whole if (!ccur).

[00:04:10]
If we wanted to do it that way, continue. And then we could do this nice little, Push it all in, and awesome. Let's see, what does it say here? Well, it saying this is not assignable. Yeah, that's because I didn't define this thing appropriately. These are more TypeScript problems, BinaryNode<number> or null, right?

[00:04:34]
By doing that, we can do this. And then why are you not working? Object is possibly null, now you're lying to me. Now you're just lying to me. There we go. I forgot to say it's an array. It wasn't just a binary node, it's an array. There we go.

[00:04:47]
So for those that aren't familiar with Java or TypeScript, this is really, really simple. I'm just saying, hey, the type can be one of these two, it's either a binary node or it's a null. And we have a list of those things. And then, when I shift it off or remove the first item from the list, it can either be the binary node.

[00:05:03]
This is JavaScript, so you can shift an empty list, so that would be undefined, there's nothing there. Or it can be a null because we have our type definition specifying a binary tree to be either a binary node or null. So that's why we have these three types right here.

[00:05:20]
There we go. And now we've just created everything except for the last part. We're not returning a Boolean at the end. If we get all the way down to this point, we've traversed the entire tree. And have we found the value? No, we haven't. We haven't found the value.

[00:05:35]
Awesome, we just did it. Now, if I've done this correctly, we should be able to npx jest, let's just try BT. I don't know how many things will run. Wow, look, all of them run. My goodness the whole section was just slam dunk. I feel like we did a great job here, all first try, it's fantastic.

[00:05:54]
I'm sure everyone is super impressed. Now, one quick question, which one do you like more, BFS or DFS? Which one feels easier to understand?
>> DFS.
>> DFS?
>> Yes.
>> Delta FS? Or the recursive one? I feel like the recursive one is a bit easier to code, if feels a little simpler.

[00:06:17]
The base case is really, it feels more understood, it does feel a bit cleaner. Iterative always tends to be more messy than recursive. But recursive comes at a different cost, right? We're calling functions, which remember, we minimally have to set the return address, the return argument, the parameters we're gonna be pushing in.

[00:06:33]
Things have to happen, unless of course, JavaScript inlines it. We don't know what actually happens in JavaScript land, but we know something happens in JavaScript land. So things happened. That's why I do tend to like the recursive side more than the breadth first side. We have another one?

[00:06:48]
>> Just Chad is mostly saying DFS, but they would like to see BFS recursive as well and compare.
>> You can't do a recursive, I mean, could you do a recursive BFS? I'm not sure if you could do a recursive BFS because you're using a stack in recursion and you're using a q in BFS.

[00:07:05]
So I'm sure there's a way to make that happen. If there's a will, there's always a way. I would have to play around with it for a little bit and kind of, my first try may not be as lustrous, but it would eventually happen. And so I'm sure we could make it happen, but you just wouldn't ever do that.

[00:07:24]
You can't do that because depth first or using a stack preserves shape. So it goes down one side, whereas you just can't do that with a q. q does not do that.