Okay, finally time to look at some source code for a binary search tree. So the source code that I'm about to show you can be found at the following link. The link should also be in the description at the bottom of this video, please like the repository so that other people can also find it more easily. And now let's dive in. All right here we are inside the source code for the binary search tree. This source code is written in Java.

Okay, so first thing you will notice is I have a class representing a binary search tree and it takes as a type anything that is comparable. We need things that are comparable so we know how to insert them accordingly within the binary search tree So to start us off, I have a few instance variables, actually only two. In fact, we're going to keep track of the number of nodes in the binary search tree, and another one, which is the root of this binary search tree because the spire search tree is a rooted tree. Next, I have a private and code class, which contains a left node and a right node as well as some data of type T. and that type T comes from here, so it's some comparable type T. Okay, next I have a method to check if our binary search trees empty. It simply checks if the size is zero.

And size simply returns the node count which gets either incremented Or decremented as we add or remove elements. Okay, here's the public method to add elements to this binary search tree. I also have a private method down here as you will notice. And I use the private methods to do the recursive business and the public method to just check if the element is already contained within the binary search tree. This insertion method will return true if we successfully insert a new element into the binary search tree and it will return false if there's already something inside the binary search tree. So elements have to be unique inside this binary search tree, okay, so supposing this branch doesn't get executed, meaning the element does not already exist in the tree then we're looking at This branch, and I'm saying, okay, add this new element to the binary search tree recursively and also up the node count by one, and return true because, well, this element doesn't yet exist.

So let's look at the recursive method now. So our base case is that we found the null leaf we want to insert our element at. So we will create a new node object with two null children. But with the value of the element we want insert. Otherwise, we're in this branch and we choose which subtree we want to place our element inside, so either so it'd be the left subtree of the first branch. the right subtree the second branch.

Okay, now let's look at removing. So here's the public method for removing, I'm only going to remove the method if it exists within the tree. So I checked if it's within the tree before, otherwise it was going to return false. Meaning we have not removed anything from this binary search string. And if it is contained, I'm also going to decrement the node count. Now let's look at this recursive method to remove the node.

So this recursive method simply has a normal base case. Let's now return null. And in the first step to removing a node, we first have to find it and we know it exists. Because of this check, we know that our element is within the tree so we can remove it. And that is these two cases. So this is like the fight Phase I was talking about in the latest video.

So I get a competitor value, and I check if it's less than so we're going in the left subtree, or we're going inside the right subtree. It's going to be one of these two cases. Otherwise, we found the node we want to remove. So this finds the node. And here's where we do the actual removal. So I talked about four cases in my slides.

But in fact, you can think of it more or less as three cases even two cases because two of the cases are very similar. So the singleton case, where there's only one node It's really that that can also be thought of as a left subtree or a right subtree case, this case is the case where the left subtree is no but the right subtree is not. And this case, the right subtree is no but the left subtree isn't. And this case down here, which I'll get to later, we have both sub trees. So let's go to the very top. So if we only have a write sub tree, then I'm going to say that the successor node is just going to be the root node of that right subtree.

So node dot right and then return that. And I also destroy the data within this note And the note itself. Similarly, for the other case, where I only have a left subtree, what I'm going to do is I'm going to reach into that left subtree and grab the root node. And I'm going to return that node. And I'm also going to destroy this node because we know we don't want it anymore. So those two cases are fairly easy.

Now let's look at the case where we have a less a sorry, a left subtree and a right subtree. So as I mentioned in my slides, we can either find the largest node in the left subtree or the smallest node in the right subtree. And here, I find the smallest node in the right subtree So I go down to the right subtree and I dig left. And this is the node or the successor node, if you will. So we copy the data in it. And then we recurse and call ourselves to remove the successor node.

If you wanted to find the lowest value in the left subtree, they could just uncomment this code and it would do just that. So that's removing and that shell now also had these two helper methods to do a dig left and a dig right. Moving on, I also have this method that checks contains an element. So given an element will return true or false, depending on if that element is within this binary subtree. And this is very simple. This is equivalent to the fine phase.

If We reach a null node, we definitely know that that element doesn't exist. Otherwise get our comparative value, which is either going to be less than if we need to go to the left subtree, meaning this case, or greater than zero when you go and right subtree. Or if we found the element, then that's zero case. And we're in this case. So pretty simple. Just as a bonus, I also threw in a height function.

So this will calculate the height of the tree. I will do some linear time, height we'll call the private recursive height method. And all this does is it's fairly simple. So if we reach a leaf node, we're going to return zero. Otherwise, we're going to return the maximum height of the left sub tree or The right sub tree, because one of our sub trees might be greater than the other. And that's going to be the one that we want the height from.

When every time we recurse, we add plus one. So this corresponds to a depth. So the biggest depth is going to be whatever the height of the tree is, if you want to think of it that way. And now for our traversals, I have created this method called traverse. And what it does is it takes a a tree traversal order, which is an enum type I'm going to show you in a minute and and that's an order and then I picked whichever order you give me now return an iterator for that particular order I want to traverse so if you tell me I want to traverse this binary search tree in a pre order fashion that I'm going to return you this iterator, which is this method. If you want to traverse the tree in order for it to return you this inorder traversal iterator.

Let's have a look at what this tree traversal order is. Let me open that up right here. So that is simply an enum type you can see right here. So it's either one of these four things, it's pre order in order post order. So nothing too crazy. And I decided to do these traversals iteratively so that you don't have to do them recursively which would be slightly slower and And perhaps less convenient, this is more flexible, although I don't really want to dive into the code because it is fairly nasty.

If I just open up, say the inorder traversal, then it does look pretty gross, I have to maintain a stack manually. And I have to check for concurrent modification errors, etc, etc, etc. These are actually great interview questions like how do i do an inorder traversal iteratively? Or how do I do a post order traversal iteratively, and so on, and so on. So, so those are definitely great to practice. If you want to actually see what's hidden inside these methods, just go on the GitHub repository and have a look, but I showed you guys how to do treat reversals in last slides.

So you should be good to do that. Most of the time, we do it recursively anyways, Just wanted to be a bit more fancy and go all out intuitively. So this is about it for the binary search tree. Guys, thanks for watching. If you have any questions, drop a comment. I'll try and get back to you.

I do read them. Okay, ciao for now.