Depth-First: Find

[00:00:00]
>> We're not seeing a new data structure at this point, right? We're just simply ordering the data in the data structure differently. So let's see, do I have, okay, good. Let's kind of whiteboard these things out. We're not going to implement all these things when we did a doubly linked list implementation.

[00:00:19]
This is like that, but just slightly worse. It just would take an hour of link playing, and so I don't wanna do that, I don't wanna do that. All right, so let's just talk about, we can whiteboard it, though. We've been whiteboarding and translating these ideas to code.

[00:00:32]
You guys can do that too. I'm positive you have the strength and the mental capabilities to do it. So let's talk about a binary search tree. Often you'll see it abbreviated as a BST. And so a binary search tree is still a binary tree, but there's a rule that has to be applied at every node.

[00:00:51]
I always draw my trees complete. So I'll just intentionally draw this one a non-complete tree. A complete tree, of course, is where all left and right is completely filled and it has the same height. So this is a non-complete tree, if you will. So what's the one rule?

[00:01:06]
The one rule that you have to be able to apply at any single node is this. This side has to be less than or equal to, this side has to be greater than. That's the only rule. Now, you could do this for some optimization, make it like that, because there is a case where like say if you had all fives, you wouldn't want just a large line going down.

[00:01:30]
And so you can make the case why you'd want to do this versus not having that blah, blah, blah, blah, blah. But for our case, we're gonna keep it pretty darn simple. We'll just hold to this single case, which is to the right, everything is larger than, to the left, everything is smaller than or equal to me.

[00:01:47]
Now, what algorithm does this already sound like? Let me try putting a P in here. You agreed yes like you knew. What is it?
>> I forgot the name of the sort, but it's one of the sorts, quick one.
>> Quick one, yeah, Quicksort. Effectively, this looks a lot like Quicksort, does it not?

[00:02:09]
We have a point in which we're at. Everything on this side or everything on that side of the pivot is this value. Everything on this side is greater than, right? That it's like it's identical in some sort of sense, and even has a lot of the same characteristics of Quicksort, and we're gonna see that.

[00:02:25]
So there you go, that is the requirement of a binary search tree. So let's talk about finding, say we want to find a value v, right? There's a v in here and we want to find it. It's kind of like Quicksort in this sense, but it's more like breadth or a binary search on an array list, or on an array.

[00:02:44]
A binary search on array, remember, we split the thing in half. And then we say, hey, are you the value? If it's the value, we leave. If it's not the value, we have to say, hey, if I'm larger than the current value, that means I'm only gonna be on this side of the tree.

[00:03:01]
If I'm less than, then I'm only gonna be on this side of the tree. And so find is effectively doing a simplified version of a binary search on an array. What you'll effectively see is that it's much easier to do a find on a binary search tree than it is on an ordered array.

[00:03:18]
It's just much simpler because you just don't have to manage this low and high business. And so let's just kind of walk through it. Let's kind of write the pseudocode. So we're gonna do find, and we're gonna be given a node, and let's just say we need to produce out a Boolean.

[00:03:31]
Is it there or is it not there? So what we can do is we can do a simple check of, if this is not like this, we're at a null point, we have to return false, right? Remember, base case is people, very, very important. And you can tell we're gonna be doing a base case or you can tell we're gonna be doing a depth first search because we're going down deep, right?

[00:03:52]
Every single level, we make the same determination, which way are we going? Okay, go deeper. Which way are we going? Okay, go deeper. So it's a depth first search with an order to how we traverse. So if it's not a node, we obviously return false, right? Can't do anything here.

[00:04:09]
We've got to the end and we did not find our value. Therefore, we know the value is not within the structure. Else, we do a simple check. If node.value, oop, I forgot to put v in here, equals v. No, my if statements are all wrong now. So if the value of the node is equivalent to the v, then guess what?

[00:04:29]
We found the value, right? So we can return true. Awesome, right? Everyone's on board? If the value of this node is less than our value we're looking for, meaning that if we went to the left, it's only values even smaller, we need to go to the right. So we would simply return find, my goodness, that is just the worst spelling of find I've seen in a long time, find node right value, right?

[00:05:03]
We need to go to the larger value section. We are too big for right here, let's go to the larger value section. Or that means there's only one condition left. We don't actually need to spell it out. It just simply means we are smaller than the current value.

[00:05:17]
So we need to go to the kids table, right? We need to go to the smaller value table. Let's go, so we find, Node left value, and there we go, that's all we have to do. If we hit this case, the whole thing's false. We've made it to the very end, we've kept splitting our array in half until we found that there is no value that's equivalent.

[00:05:35]
Or we find the value, so we return true. Everything makes sense? I think binary search trees are pretty awesome. So if I were to write one in, I would put something like this in here, right? 17, so that means everything on this side of the tree must be what?

[00:05:53]
Smaller, right, or equal to. So I mean, technically, I could rewrite 17 again, which we will. And that means this value is kind of interesting. Can this value exist? If we have this condition right here that it must be larger than 17, and we have this condition right here, which means that everything in this subtree must be equal to or smaller than, can that tree exist?

[00:06:19]
No, it can't, cuz I'd have to put something like 18 in here, which breaks that, right? You couldn't actually have that in there. So even in this case, we can't actually even put 17 in there, so let's put something like 15. So quick question, can we now put something right here?

[00:06:37]
Yes, we can put 16 or the value of 17. So we'll just put 16 right here. Here, we can put 4, right? Have we preserved the case for the upper subtree or for the upper tree? Yes, we have. Here, have we preserved the case? At this point, is everything on this side larger than my node?

[00:06:55]
Yes, it is. Is everything on this side smaller than or equal to my node? Yes, it is. Awesome, so we've preserved the case. So that's the only requirement of a binary tree is that we keep on recursively putting this in. So I'm gonna have to be kind of careful on what value I choose here.

[00:07:10]
So I'll just intentionally choose a large number, and then I can choose a smaller number. And so now that means this node right here can only exist within the values of 26 through 50, right? It can't be any other value. You have a question?
>> What's the functional use for this?

[00:07:28]
What would you use-
>> Functional use is QuickFind, and we'll see why that is the case.
>> So this is just a way to put IDs on something to connect it to something else? I mean, you're just quick finding numbers that you put in into it?
>> All right, so the question is what's the use of this?

[00:07:44]
Why would we actually use this? What it is for is for quick finding, and the reason why it's for quick finding is, imagine we had a list of things we wanted to search through. Well, you already have the list, but what happen if I wanted to start adding to that list?

[00:07:55]
What happen if I wanted to start removing from that list? It actually makes addition and removal kind of hard on these lists because now you have to grow and shrink your array. Plus, you have to be able to find the spot in which you want to add or remove from.

[00:08:07]
And if you add, you have a worst case of an n running time on an array.
>> So this is for adding to the list? So if you're-
>> If you have a dynamically changing.
>> Okay, yes.
>> So as it changes, you're still able to search at a reasonable rate, but that does come with some level of consequence.

[00:08:23]
The good part is just like a linked list, you can add anywhere at the constant rate. But there's traversal costs, and B, things can kinda get a little bit out of sync when it comes to a tree, and we'll see that here shortly. All right, so this node can only be in this value range, right?

[00:08:42]
Awesome, what value range can this node be in? 18 up to 25, right? That's the only ranges it can be in. It's really good to be able to understand this and kind of walk through the exact shape of a binary tree. We do have a question.
>> The right side should be greater than 17 or can it also be equal to 17?

[00:09:04]
>> I did kind of mention that a bit earlier. If it is equal to, we can certainly do that. And I think, imagine if you had a bunch of very highly repetitive values, say 5. If you insert it over and over again, which we'll see the insertion algorithm here shortly, you could imagine a world where you have this.

[00:09:20]
5 points to 5, which points to 5, which points to 5, which points to 5, right? You could actually create effectively a linked list and call it a tree. And so there is some value in highly repetitive structures having it so that both sides can be less than slash equal to, or greater than slash equal to.

[00:09:37]
>> So if you're adding 51, then you have to start another branch?
>> If we add 51, we would have to start another branch this way, cuz that side is permanently greater than, right? So we're actually gonna do insertion right now.