‫So now we're going to create our binary search tree constructor.
‫But before we get to that, we have to create our node class for a binary search tree.
‫And as we have discussed previously, this node is similar to an unordered map that looks like this.
‫And we'll create our member variables for our node class like this.
‫And then we'll have a constructor for the node class that we pass a value, and we'll set this value
‫to be equal to value.
‫This is the same as we saw in a linked list node.
‫And then we'll set left and right to be equal to null pointer.
‫So now we can start building our binary search tree class.
‫So for the first thing I want to explain in building the binary search tree class, I'm going to bring
‫up a node and make it part of a tree like this.
‫So all of these nodes need to have something pointing to them or you're not able to get to them.
‫And you can see that all of these nodes have something pointing to them, the node above it, except
‫for one.
‫And we saw this with linked lists.
‫We have to have something pointing to that first node we call that head.
‫That is a requirement.
‫Tail is not a requirement.
‫We saw that when we used a linked list to implement a stack where we had top, but we didn't have bottom.
‫So I'm going to put this back as a binary search tree.
‫And what we're going to call the variable that points to that top node is we're going to call it root.
‫So now I'm going to bring this code back and our one member variable that we're going to have is going
‫to be called root.
‫So now let's create the constructor and we'll focus just in on this.
‫We're passing this a value.
‫We use that to create a node like this.
‫That will say route equals new node like this.
‫And this is how we have created our constructors up to this point in linked list, doubly link list,
‫stacks and Qs.
‫We created the first node at the time that we created a particular instance of that data structure.
‫Doing it this way is completely valid, but I'm going to show a different way of doing this.
‫Instead of creating the first node at the time that we create the binary search tree, we can also create
‫the binary search tree to be empty at the time that we create it.
‫And then we put the first node in the binary search tree with the insert function.
‫So I'm going to bring back our code and our constructor and change it to make it do this.
‫And I'll go through line by line.
‫So that first line, we don't need to pass this a value.
‫The only reason we pass this a value was to create the first node so we can remove this.
‫This line creates that first node so we don't need this.
‫And then instead of saying root equals new node, we're going to set it equal to null pointer.
‫So if we're going to create a binary search tree this way, this is all that we need.
‫And the constructor, you could do something similar to this with linked lists where you set head and
‫tail to be equal to null pointer and set the length to be equal to zero.
‫So now let's put this new updated constructor in with the rest of our code.
‫That is our entire binary search tree class so far.
‫And now let's go over to VZ code and take a look at this.
‫So there is our code for our node class there and I'm going to scroll up.
‫And this is the code that we just looked at for the binary search tree class.
‫This line creates a new binary search tree called my binary search tree.
‫And then with this line, what I want to do is I want to do a see out and show the root.
‫And obviously this is going to be equal to null pointer.
‫But to get access to the root, I need to come back up here and change this from private to public.
‫Otherwise we can't access that from the main function.
‫So now I'm going to run this and you can see that the root is pointing to null pointer.
‫So it looks like we have a working binary search tree constructor.