Four Semesters of Computer Science in 5 Hours Exercise 8 Solution

Transcript from the "Exercise 8 Solution" Lesson

[00:00:00]
>> [MUSIC]

[00:00:02]
>> Brian Holt: Okay, let's talk about binary search trees because this stuff fun. I like it I get excited about binary search trees. So again, I just want to reiterate reiterate to everyone. This is hard, right. This is not simple to achieve and furthermore I'm compressing a lot of content and that's a lot of cognitive drain throughout this entire day.

[00:00:27] So, this is not like if you feel yourself dragging a little bit, I profoundly understand. Okay so we're gonna do ad. So the first thing we need to do, is we need to check, do we even have a root? Right, because we can't really do anything if you don't have a root.

[00:00:43] So, if this.root equals null, meaning we haven't added anything to the list yet, gonna say, this.root = new Node(value). Okay, a plus, we now have a route which is good. And here, I'm just gonna say return cuz then you don't wanna do any of this other stuff if you create the node.

[00:01:12] So, let's go ahead and do the rest of it. So, I'm gonna say, let current equal this .root. This is gonna look very much similar to finding something in the link list, right? It's kinda the same idea. And I'm going to change just to X describe because I don't wanna set off an infinite loop with what I'm about to do.

[00:01:37] So, let current = route and then I'm gonna do which will look really weird to some people a while true loop, which basically means that I want this to keep running until I explicitly break out of you, right. And the reason why we can do this is that if you're adding a new value to a binary there's always a place to add it, right?

[00:02:04] It should never actually not find a place to add it. So that's why it's okay for us to do a while(true). Okay, so if (current.value) Is greater than that value. That basically means we need to go left, right? So, go left and then else go, right. So, when you're kind of skeletoning these things out it's kind of helpful to put these little code reminders in here for you,okay.

[00:02:45] So, if current start left then current.left then current is assigned current.left. So basically, we're saying if you have a left child now I'm gonna move my pointer my current pointer to the left child and rerun this loop again, right. So it's basically saying, okay I'm gonna run the loop again, right?

[00:03:10] If it doesn't have a left child then at this point we found the spot that we need to add it in, right? So, we're going to say, else current.left is assigned. New node with the value and then return because we're done. We found the place add it and we're done.

[00:03:37] You can also do break here. If some people don't like having multiple return statements in a loop or in a function that doesn't really bother me so I do return. But you're also welcome to do break as well.
>> Brian Holt: Okay, so as you might imagine, go right is pretty much the same thing.

[00:03:57]
>> Brian Holt: So, if current.right,
>> Brian Holt: Then current is assigned current.right else current is assigned or current.right. They do it right up there as well so yeah, okay. Current.right is assigned new node with value. And then we just return because we're done. So, now, hopefully I can go ahead and change has to be described and we have a correct looking tree.

[00:04:35]
>> Brian Holt: Any questions about this? Does that make sense for the most part? Or is it just like black magic and I'm waving my hands around say look at the cool code things. Cuz I can totally be doing that too.
>> Brian Holt: Let's just conceptually walk through it again in case anyone missed it.

[00:04:52] So, the first part is, no head, create a new head, right? Like that's this first block right here. So, if you have no root or head or whatever you want to call it, create a new head and then return. So that's the, like the edge case, right? Okay, so the first we're gonna do is we're gonna grab the root and say this is the node that we're currently looking at, that's why I call it current, right?

[00:05:21] Then we're gonna have a while true loop that's just gonna loop over as many times as we need, right? And we're gonna say hey, current dot value, this no that I'm inspecting at this moment time is your value greater than the value that I'm trying to find? If it is then you need to go left because you need to be in the smaller part of my tree, right?

[00:05:43] That's basically we're currently seeing here. That's saying if I have a left child then run the same process with my left child as current, right. So, you're just moving from three to one, right. So, we're just moving and zigzagging down the tree, yeah.
>> Brian Holt: Else if I do not have a left child then you have found the spot that you're supposed to insert this, so create a new left child and then you're done get out of here.

[00:06:12] And just the mirror image for, right. Okay.
>> Speaker 3: If you allow duplicates finding Z for example if you like to because you have to follow the loop until you don't get a result back? If I will find all the duplicates. And you go.
>> Brian Holt: And if you want to find all the duplicates.

[00:06:40]
>> Speaker 3: Again, the first night seems easy, but finding the second nine, third nine?
>> Brian Holt: Right, so you have to have, I guess, a knowledge of do duplicates get added to the left always. So basically, you're gonna keep looking for nines, and just adding them, or keeping track of the ones that you've already found.

[00:06:57] Until you get to the place that you would add a nine, right. And then, at that point once you've reached what's called the leafnode, right. Then you know that there can be no more, right. So basicall, you just follow that pattern through to exhaustion basically good question. Yeah.

[00:07:17]
>> Speaker 2: Dan H has a question about, what are some practical uses for a binary search tree?
>> Brian Holt: The practical use for a binary search tree is when you have ordered data, ordered in the sense of, it can have can be ordered from 0 to 10 or A to Z or something like that, and you need to be able to search for nodes very, very quickly.

[00:07:40] I know underneath the hood a lot of some databases are done with trees don't ask me specifically which because I don't know but specifically when things need to be searched for fast like I'm going to guess maybe something like the last six search of total guess but maybe something like an elastic search.

[00:07:58]
>> [INAUDIBLE]
>> Brian Holt: I'm sure they use trees everywhere or like in auto complete, I could see using trees very well because you. I write A, then I write AB and it's gonna go down this pathway until it finds things that it can auto complete for me. I could see that being a very useful case for an ordered tree like this.

[00:08:19] Good question.