Binary Search Tree Practice

[00:00:00]
>> So, let's go edit on code is code sandbox. Top over to trees or I think they call it bst right here, bst.test and I want you to implement I think I just have to add I don't think I actually have you do. Let me just check to make sure that I asked you to do the right things.

[00:00:38]
So I just have you do add, I don't actually have you ever do delete. So as a stretch goal, maybe later when your brain kind of recovers from learning all this stuff, you might come back and try and do deletes. But for now, let's just go ahead and stick to adds, so let's actually just kinda get you started here.

[00:01:01]
Bst, So I might give you a constructor here and just set this.root = null, it's probably a good one to do right away. You're gonna do an add which is gonna take a value,okay. So you're gonna have to have some logic around,if this is the root. Okay, and then you're gonna have to do some sort of find the correct place to add.

[00:01:50]
And so there's two ways you can do the add, here in my particular course notes, I do it via a while loop, so this could be or. Another thing you could do here is you could create a node class down here, that's a constructor that takes a value.

[00:02:13]
You'll say this.value = value, you'll say this.left = null, and this.right = null. You could potentially if you wanted to create an add method on this, that takes the value and then this could be called recursively. So that's another potential. We'll be doing it with the while loop here but just know that's also another possibility here, depending on how you wanted to do it.

[00:02:50]
And then The other thing that might be helpful. Is if you do a toObject method here and just return the root, so this return.root. I actually wrote a little visualization helper for you. So if you hop over to The source here and look at tree.js. This will actually help you visualize your whole app here if this will load.

[00:03:44]
So you can see here I had this tree, if you return it to an object and it has value left and right. You can ignore height, cuz we'll talk about height here in just a second, so ignore height. But if you pass it a root node that has left and right nodes, this will actually visualize it here for you as well.

[00:04:08]
But you don't have to do that right now, I'll show you how to do it when we do our solution together. For now, just get all the adds working correctly.
>> How is this any different from running a binary search on the sorted array?
>> How is this any different than running a binary search [INAUDIBLE]?

[00:04:26]
Well, one's an algorithm for finding something in a sorted array, and one of them is a data structure used for storing information. Now you might ask, why would you ever use a binary search tree over something like a sorted array? And it has to do with how you would allocate things in memory, right?

[00:04:46]
So for a sorted array, you might try store that as a, an array list right, where everything is laid out sequentially in memory. Which is not usually gonna be possible particularly for something like a database index, right? Cuz those database indexes could be pointed to objects that are enormous, right?

[00:05:02]
So this would be more, something where you cannot be constrained by the memory you can kind of point to wherever things want to be in memory. There's other uses for trees too, that's just kinda the most classic one and the one that I have in my head at the moment [LAUGH].

[00:05:20]
But it's, yeah, I guess at the end of the day one's a algorithm for finding things on a sorted array and one of them is a data structure for storing lots of data in memory or on disk for that matter. So, it depends.
>> A big chunk in the heap memory, you can just sprinkle it around then use pointers to [INAUDIBLE].

[00:05:44]
>> Exactly Yeah,
>> It's less prone to, it's fragmenting the memory alert, but it can find the space for itself easier on a fragment, yeah, right. Fragmentation is something far less concerning these days with just how memory works, right. It used to be much bigger concern, but, and in fact in this case, it's helpful, right, because we don't have to worry about knowing ahead of time how much data we're gonna allocate.

[00:06:19]
So the first thing that we're gonna wanna do, with our tree is, just gonna erase this. If this.root ===null, then we need to create the root, right. So we'll say this.root = new Node(value), right, that's it. Otherwise wanna say let current = this.root, and then we're gonna use a while loop to try and find where it should go.

[00:07:00]
So we're gonna say while and let me make sure this is not running when I do this because we're gonna write a quick while true loop, cool. So we're gonna do a while true loop because we want this loop to just keep running until we tell it to stop, right.

[00:07:31]
There's always gonna be somewhere to put the add or to put this new node. So we're never going to run into a place where we don't wanna it. So that's why this is an okay opportunity for us to use a while true loop. So first thing I'm gonna say is if current.value > value, then go left other otherwise go right, right.

[00:08:07]
Then inside of here we'll say, if there's a current.left Then we're gonna say current is assigned, current.left. I mean, the loop run again. If it's not then we're finally supposed to add it and we say, current.left is assigned new Node with value. Okay, if we go right then we're gonna say the opposite logics.

[00:08:42]
If current.right Then we're gonna say, current is assigned current.right and we let the loop run again. Otherwise, we say current.right is assigned new Node with value Okay, in these two cases here 36 and 44, we're gonna say break. You could also just say return, which is fine as well.

[00:09:28]
But I'm gonna say brake. If you're not familiar with brake, it just basically means, hey, I'm in a loop right now stop being in the loop,okay. And then I need to get out of the while loop, out of the else, in every case I'm going to return this, which is the tree itself.

[00:09:55]
Okay, and then two objects just returns this.root, so that's okay. So, this should work, let's try. And let's just make sure that I take the skip out of here, I did not So let's try that again. And bst test is working, cool. So for funsies let's paste this over into our visualizer.

[00:10:39]
Let me go over here into tree, and I'm just going to paste this right here. Then we're gonna pop over to our little tree visualizer here, and you can see, this is what my tree looks like. It's very large at the moment, maybe a bit too large, let's do something much smaller, maybe with 10 elements.

[00:11:05]
And so you can see here, it helps me visualize what my tree ends up looking like, kinda cool, right? So you can see this binary search tree and particular in this case, it's not super balanced, right?. So if I try and find 4, I have to go through 92867 or 86534, till eventually I find 4, it'd be great if it was a little bit more balanced, right.

[00:11:43]
In the sense of, everything was a bit closer to the root and it was kinda laid out better, we're kind of at the mercy of how the numbers are added. For example, if I don't shuffle these, let's just visualize what this looks like when I say, const nums =.range(10).

[00:12:11]
What did I do wrong here?
>> You forgot to [CROSSTALK].
>> Yeah, it's getting late in the day, my friends. So this looks really hairy. So you can see here I got 0, and then it goes to 123456789, right? So it's all just in one leg. So if I search for 9, I got to go through 9 hops.

[00:12:37]
This is why you're actually not gonna see binary search trees, in production ever just normal straight binary search trees. Because they run into these worst case scenarios and it's not that uncommon to see him, right. So we're gonna talk about another one called avielle trees that mitigate this, but there's lots of strategies for doing this like red-black trees and other ones that I can't think about top my head.

[00:13:06]
But when you get a random distribution like this, this isn't terrible, right? The max depth here is 6. Or let's do 50 again. Max depth 11 I mean not great, but it's a lot better than searching through 50 things, 11 is more palatable. How about 150? 15, so by tripling it I only added at most four more hops.

[00:13:29]
950, 20 right, so you can see, this is where the logarithmic lookups really help, right? So now I have 950 elements in this array and at most I have 20 hops to find what I'm looking for. It's not too bad, right? But, if I change this to const nums down here, in fact we can just do it, and I did 100, right, this is the worst case scenario now where I have max depth of 100.

[00:14:03]
If it's unclear this line 56 here is adding them in order, right, from 0 to 99, as opposed to 55 is taking the same numbers but shuffling them in some random order.