Implement Depth-First Search

[00:00:00]
>> So I think we have one last thing to do, which is we're just gonna write a binary search. We're not actually gonna write the insertion or the deletion. This should only take like a minute or two. Very simple operation to do, so let's do that. So let's go back over to our sweet coder machine and go to binary search.

[00:00:18]
What do I call it? No, I think binary search list is not the one we want. Yeah, I bet it's BST. Yes, DFS on a BST, there we go. [LAUGH] All right so of course we're gonna start at the head, we're gonna go with the needle and we're going to return true if we found it if not.

[00:00:41]
So the good part about this is that we don't even have to write a second function right? We should be able to just tell right away actually we are gonna have to write a second function. Let's call this thing search and do a current and call it a BinaryNode, which I think I hard coded the generic in here.

[00:00:57]
It just makes it easier to see in class. We don't need to be generic over t, as BinaryNode or null, and then the needle number and then Boolean if we find it. So again, base cases, base case is super important. What is the most obvious base case?
>> Null.

[00:01:17]
>> Yes. Null, someone said null. There we go Graham technically said null. If not current, return false, right? We have made it to the bottom of our binary tree. It's null, therefore our value is not there. We've exceeded the height cuz remember, we're either saying hey we're less than this value so we must be in the smaller section or we're greater than we must be in the greater than section.

[00:01:37]
Therefore, we will find it or we will hit the null note eventually. All right, so we're here. So what's the other base case? Equivalence, right? If current dot value is equal to the needle we are searching for we have found the value correct. Awesome. So therefore we can return true.

[00:01:59]
There's no need to keep on traversing. That'd be like you know the phrase it's in the last place I looked if you kept looking after you found your item it would be silly exact same thing here it's always in the last place he looked. So therefore we have to do a traversing so if we didn't find it.

[00:02:17]
If we're neither null nor we contain a value we need to traverse. So we like this if, current.value is a less than or current value we're looking for. We need to go to the right hand side of the tree right? You have to remember it's always backwards to this thing.

[00:02:35]
So that's why if you write it out correctly, you can use this whole I always do this. You can use that exact same thing long as you do the value and then this match up the symbol I go to the right. Just a little kind of like a little mental ease, right?

[00:02:51]
All right, so then we're gonna return search with current.right and of course needle, right? We're gonna return the results of that side cuz either we're gonna make it to a null point or we're gonna find the value. Else, we simply do the exact same thing and we're just gonna have to search on the left hand side right?

[00:03:08]
That's really our only two possibilities. Notice that we're not doing both sides, we're only doing one side or the other that is the beauty of a binary search is we're reducing our search space by half every single step and we're only checking once, we're not checking in we're checking once.

[00:03:24]
So greatly reduces our time effectively, log in on a perfectly balanced tree or really running time of height Yeah, it was pretty easy. Yeah. Then we have to do the actual, hey, call the thing so return search head, needle. Yeah, there we go. And if I am a liar, this thing won't run mpx jest BST.

[00:03:53]
Okay, see, it's really not that hard. It really isn't that hard, binary searches aren't actually all that hard on trees. That was much harder on an array, correct? Here let's see if we can open this up. I think I did that on day one. Let's see, what do we call this thing?

[00:04:09]
We called it a binary search. Yeah notice like this was the algorithm there that is much harder right? We are controlling our midpoint, we're effectively finding the node in the tree controlling the midpoint but the good news is this is always log in, right? This is 100% of the time login cuz we're always guaranteed a perfect split each time.

[00:04:30]
Whereas on our previous one, my goodness, I should have marked it. Let's see, BST, there it is. We have no guarantee that one side is gonna be perfectly equal versus the other side. So we just simply have to walk it. Our lows and highs are predetermined for us.

[00:04:46]
And that's that.