Four Semesters of Computer Science in 5 Hours Exercise 8: Binary Search Tree
This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Exercise 8: Binary Search Tree" Lesson
>> Brian: I'm gonna show you both ways, but you can do a binary search tree, both recursively and iteratively. I'd actually do it iteratively, meaning you can either use recursion, or loops, right? That's what I actually mean. I'm gonna use loops on the binary search tree, but when we move on to AVL trees, which is our next section, you actually have to do AVL trees recursively, so it's up to you if you want to do recursion.
[00:00:28] And just think of this in terms of, well, if I call it, if you want to do it recursively, if I add seven here, let's say five [COUGH]. Well, it doesn't go here. So, I'm gonna call add, so I call add on eight with five, then I'm gonna call add on three with five, then I call add on six with five, right?
[00:00:51] Just calling out on each node as you go down, right? That's how it works recursively as opposed to using iteration. Does that make sense? So basically, you're treating, I mean, you can think of binary search trees like this, right? This is a binary search tree right here, right?
[00:01:09] But, this is also, this little subpar, I bring up my right here. So, this right here, if you look at it just that, that's also a binary search tree, right? So, if this has an add method on it, I can just call the add method on that, right?
[00:01:28] And then, this right here has a yet smaller binary search tree, so I can call add on that. And then if I call add right here,right, it doesn't have any children, so it can just go ahead and add itself. So that's how you're just making this bigger problem smaller and smaller and smaller until you can solve it, right?
[00:01:44] That's how it works recursively. Now if you want to do it with iteration you can say, okay. It goes here then here then here right? So you just basically use a loop to wedge a way down to the right place. That's the way I'm gonna do it for the binary search tree and then I will do it for the avl trees.
[00:02:01] Okay, so, if anyone was wondering. So, exercise. Both of them are incorrect by the way. As you might expect everything with Loops over recursion tends to be faster, but in this particular case, go ahead and do whatever suits you best.
>> Brian: So, a couple ways you can do this, name your class Tree, first of all, or else it's not gonna work.
[00:02:32] I'm going to have one suggestion to make another class called Note again like you did for linked lists. You can also make every tree like have sub trees, so a tree has two trees as children. It's like recursively defined classes which is totally OK. Just like what we were talking about We're talking about here.
[00:02:52] Right like this is a tree. This is a tree. This is a tree. This is a tree so. Either one of those is fine. However you choose to do that but just make sure whatever you have has left and right nodes. And Yeah, and make a BST, BSTree, binary search tree.
>> Brian: There is tree visualisation helper. As long as you call things value, left and right in the nodes, the data visualization helper can do it. So if you wanna see what that looks like, let's just take a look at the answer.
>> Brian: That's what the data visualization helper's gonna look like.
[00:03:41] And it's gonna show you what your tree looks like. But again, you have to make sure to call it value left and right, or otherwise it's not gonna find it.
>> Brian: Okay, so
>> Brian: You,
>> Brian: I didn't describe what method you're supposed to make but. So it creates a binary search tree.
[00:04:08] And then you're gonna need a method called add.
>> Brian: And I call toObject. Okay, well. So, let's just go ahead and program up the basic gist of it. So we'll have Tree. It's gonna have a constructor. And you're going to say this dot root equals null right? Because it's not initially going to have a root.
[00:04:33] Okay, you're going to have a two object method to be able to do the visualization helper. You can actually just say return this dot root and that's totally fine. And then you're gonna need an add method where it takes in a value and it does interesting things with it.
[00:04:59] Then down here you can have a node if you choose it to do the way I did it. Class node and it looks remarkably similar to our other one. Constructor. So I'm gonna say value left equals null right equals null. And you're gonna say the dot value. this.value equals value.
[00:05:27] This stuff left equals no or so it equals left and this start right. Equals right. These are just the fall parameters So if you don't pass anything in from right it's going to just assign it to be known Same thing with left. That's all that does. And great, so now all I really need you to do is do add.
>> Brian: Keeping in mind that when you first create it, you're gonna have to create the root right? And the other thing is you don't have to do delete because deletes are a pain in the butt and you can do them later. But the basic idea with the deletes is you just move up nodes.
[00:06:07] Well anyway we'll talk about that afterwards and just kinda briefly breeze over what a delete looks like. In this case just go ahead and do add. And I'm gonna give you 15 minutes to do that.