OK, so then to another video in this video, we're actually going to go ahead and implement our binary
search tree and put just a few basic functions into the implementation like insert.
Of course, we all need to create it and we'll have a find function and then we might do a sort of an
order traversal that will print out all of the values in order.
And we might add another function, we'll see.
But I have created a new project here, I'm just calling it BFD Record because I'm doing this recording
for this, but you can go ahead and open up a new project in theline and just call it whatever you want
and went ahead and made a main file here, which I will be tweeting this at some point.
But I'm telling you this line, of course, and putting my own values in the client file.
But to get started, I'm going to go ahead and make a node class similar to how we did with the linked
list.
We're going to need nodes with pointers to make our binary search tree, so we're gonna need that left
pointer right pointer.
Let's go ahead and get started on that.
So we go here and make a new C++ header file, and I am going to call this tree node.
Yeah, someone neutrino.
H.
And I'm not sure if you will have gone over this by now, but what I'm going to do is actually put my
implementation here in the header file.
So you may already be familiar with this, but just in case you're not, you can put your implementation
in the header file as well, and I'm going to do this with a sort of more modern syntax for my constructor.
I am going to use a I'm actually out two constructors and I'm going to use an initialization list for
that.
So let's go ahead and see how this will work.
So in my public section, I'm going to put a constructor here and then I'm going to do something like
this.
I'm going to need a left and right
pointer here, and I'm initialize them like this and these parentheses.
So I'm going to say no pointer, right is null pointer.
And then I'm also going to need my data, just like the link list.
And so this will be my data member and I will initialize at the same as well initialize it to zero because
we're just going to be storing integer values in this tree and then you finish off the initialization
list with just some empty brackets like that.
And it's probably as complaining because we didn't make those memories yet, so I'm just going to make
those right now, I'm going to say these are going to be tape trino the pointer.
So I am going to say to, you know, point her left and right and then my data is going to be an integer.
I'm actually going to call that underscore data just like I did up there.
OK, so yeah, this is kind of a different syntax, of course.
Like I said, you might have already seen this.
This is an initialization list is just another way to write your constructor here.
So I'm also going to have another constructor that is able to take an integer already like a value and
initialize a tree with that first initialize a node with that value.
So it's going to be another initialization list.
So I'm going to do the same thing and say left and right are no points here,
but then data is going to be set to the past integer, and I actually didn't even add that in there
in my bed.
Do it.
And so there we go.
So now we have a second constructor there.
I'm going to make a function that returns my left pointer, which is going to be I'm going to call this
left sub tree.
So as you saw in the if you can think back to the drawing of the binary search tree, I'm going to want
some getters on.
And setters, similar to how we had for the link list we had.
Previous Next.
This is going to be very similar, but it's going to be called left cemetery and right cemetery because
it's going to give you access from a given node to that nodes left cemetery and right cemetery will
be able to do some setting and getting these values.
So let's go ahead and do that.
So I'm glad you left cemetery.
And this is going to return.
He left.
And then I'm going to say tree nude, right, some tree.
And this is going to return, right?
And then I'm going to put these centers here, so I'm going to say left Sochi is going to be void and
passing a tree node and now.
So while I'm doing this, just remember back to what we did for a linked list because it's very similar
and I'm actually going to just declare.
This object to that calling object in here, and I must say this arrow left equals left, so that'll
be able to set a node left pointer correctly
and I will say right some tree.
So this is just like some overloaded functions here, I guess.
Not really, since they return different values, but kind of like that.
So
I'm going to do the same thing, right?
I'm going to say this arrow right equals right.
I'm just past doing.
Cool.
So that sets a note left and right some trees and also retrieves a node's left and right, some trees.
So we're all set up with that.
And then of course, I'm going to do that.
Get her combo with this ampersand to be able to return our data like we have already done before as
well.
All right.
And that is actually all we're going to have here for our node class.
It's kind of nice.
That's why I wanted to do it this way.
It's just nice and compact here.
We have just a header file with our implementation and now we have a full binary search tree node class
setup.
OK, so let's move on to the next part, which is the actual tree.
So if we're still using a comparison to the link lists that we've done, we would have made the L.A.
class now.
But it was our tree node and we have to make our actual link list class.
And so same for the tree.
We're going to have to make our binary search tree class now.
So let's go ahead and make that.
So this is going to be a C++.
Actually, I'm going to make the header first and I'm going to do the header file here, so I'm just
going to call this beast from binary search tree.
All right.
So I'm, of course, going to want to include my tree node tree node h and then I am going to be using
namespace
D, Class B s t d public.
I do my constructor here and this one, I'm going to have an implementation file.
So I'm just going to leave this here like a prototype.
I'm going to put my destructor didn't do that in the node, but I'm going to do it right here right
now.
So we'll do an insert function.
We're going to have to insert a value.
When I make a Boolean function that tells us whether something exists in the tree, we're going to pass
a value to it and it's just going to be called find so we can find a value to see if there that value
in fact exists in the tree.
Then I am going to do a size function.
So we'll do that.
Going to do.
In order down of the tree is what I'm going to call this.
This will be our in order traversal.
So I'm just like, you know, you dumped the values of the tree.
I'm going to do only those functions for later.
Actually, yeah, I might actually do another fine here.
So I'm going to do it.
We might go over an introduce one and we'll go ahead and just do that right now.
We may get to implementing that today might be in the video, but only go ahead with that here.
OK, and the thing is, is that we're actually going to have to make another version of a lot of these
functions because we're going to be calling it from the client file, like calling each of these functions
that we wrote here.
But since a lot of them are going to have a starting at a root node member here, as you'll see that
I'll actually go ahead and just do that right now, I'm going to make a type tree node pointer that's
going to represent the root of the tree.
So that top value.
If you think back to our picture of the binary search tree, I believe it started at 10 or something
in that lecture.
It'll just that was our roots.
So we're going to need to make a root and pointer for root.
And then I'm also going to have size here as well.
And so, like I was just saying, these will be what we're going to be calling our client file.
But since we want to start it through, we're going to make another function.
So each one of these will call another function that does the actual work, and it'll be passed the
root node quite often, so it can start at the root node to do the recursion and go through the tree.
So that's why we're going to have like multiple versions.
We're going to use encapsulation to make sure our client file is just accessing them by passing a value
or just calling it without a parameter or argument.
And then the actual work that references our private data member route will be done in another function.
So I'm going to say tree node pointer to be returned by this insert function and it'll take this tree
node.
I'm just going to call node that would be representative of the root value.
And then I'm just going to say and be there for the value, then I'm going to have my size function.
I'm going to actually, it's my fine.
So at that find it's going to be a boolean actually ran find tree node node in the value and then I
am going to do my size.
So my size function as a tree node
node
was just node.
Yeah, OK.
And then I'm going to do my in order dumbed
down and we will take you to node known, which will be the roots.
OK.
So I think I have them on there except for it or find I did not do that.
So, yeah, well, I'm not sure whether I'm going to do that 100 percent yet, but I'm just going to
leave it in the header there.
We might get into that.
We might not.
So I'll just keep it like that.
So let's go ahead and go to our implementation file.
OK, so I go up here.
I'm going to make a sauce file and I'm going to call this GST.
That's BP.
OK.
So go ahead and make that constructor actually going to include myself for first.
So this is going to be three known going to need A..
And then, of course, our current head in that we've just made so you h.
And then I think we're just going to include extreme here by reprinting some stuff out.
I think.
And that is all I'll include for now.
Do you say namespace?
Let's go ahead and make our constructor here.
So we will say ridge equals no pointer size equals zero.
And then for my destructor, it's just going to be like a default saying, so I'm actually going to
take this suggestion here and just do that.
And let's see, we have our concert and my concert function is going to actually use.
I think I'm actually going to use my fine function.
So let's do that first, actually.
So.
It's kind of me a little bit out of order, but it should still work out, so I'm going to do.
This find, and I'm going to say to me, no, no.
And the lips red tomasello.
So I'm actually going to do this, this is a client find, and I'm going to just return find, is this
going to call the other find that passes root and the value?
And then I'll do my actual implementation right here.
So I'll have the tree node cleaner and which will be a root because you can see it's been passed there
and then I'll have the value being passed as well.
And so let's look at how we would do this find function.
So we're going to need a base case and our base case is going to be if the node, which would be originally
that route planner in this past will be traversing different nodes and going to say if node is equal
to no pointer then and actually, I don't need those brackets.
I'm just going to say return false.
Then what we want to do is define nodes.
Data is equal to the value that was passed.
We want to return true.
Then this part and this next part, what we're going to do is decide whether to go left or right.
So this is kind of like a pre-order traversal that we're doing here.
So we are going through and we are checking for our value here.
And we're doing we're going to say if the value is less than the current node's data.
In that case, we're going to return recursive call of node and it's left century.
So this whole sinister left some tree or else we're going to need to pass the value.
Otherwise, if that's not the case, we don't even need for an else here because we have that return
there already.
So I'm just going to say return find.
And the other case will be that we take the opposite direction, which will be the right century and
we'll pass the value as well there.
So basically, we're just saying like if we found the value, just return true, we do need for the
base case to check, to see if we're at a null pointer before there.
And then afterwards.
We are saying that if we didn't find the value and the node is not no like we haven't gone off the end
of a leaf node and seen that the direction we went was now no in its return nil point.
We will then just be going left or right based on the value when it's less than or greater than.
OK, cool, so now that we have that function out of the way, I'm actually going to use that for the
insert function here.
So we're just going to be calling find here.
So I will say if we don't find this value in there already, and the reason I'm doing this is really
just because I know that I said that it could be less than or equal to when we were doing the tree as
far as like if we were to turn left or right, you know, would be like greater than.
But what I'm going to do here is I'm just going to have it not put the similar similar values like we
already have a value on that to you.
We're not going to like put another value in there of the same, you know, the same value.
So that's why I'm going to use this find.
So I'm going to say if we don't find that value, then I'm going to say root equals insert root value.
And then I'm going to do my actual implementation.
The non client, Colleen won, so I will miss returns a pointer I'm going to say yes to.
And search, and we want this one.
So for the insertion, my base case is going to be if node equals null pointer again and then I'm going
to say return new tree node.
And this is why I have that other constructor there for the value because I'm going to create a new
node that has the value that were passed into it.
And so that would be inserting that here, and, you know, if we were to turn back back to here and
we're saying equal to that, so I'm going to say if no data is less than three, then we're going to
say that
nodes right cemetery.
And here it's going to be.
Nodes are actually it when I'm going to do is I'm going to say insert.
No race actually died.
And then otherwise.
I'm going to say.
No less surgery.
And then I'm going to call insert no less surgery value.
And then down here, I'm just going to say we turn no.
OK, so that should be all set up if you can look through this function here.
Think back when to when we have the lecture and we were talking about inserting.
If we're at a null pointer, that means that it's basically at a leaf node and we are ready to insert
a new node to the tree there.
Otherwise, we're saying if the node data, which is like Root, it were to seen originally, if that's
less than the value that was passed, we are going to say that this node race tree is going to be set
to a recursive call of the rice tree and the value so that kind of like trickles down and sets everything
accordingly there.
So that's why we put the recursive call in here because we're wanting to set it to potentially the a
new node that we are creating right here.
And then we have the opposite case for.
We have the opposite case here where we're going down the list of, gee, I think I said this was the
loss of Gee by accident, I might have said that, but we're doing the right cemetery first because
we're seeing if the nodes data is less than the value as the current node we're at, and that would
mean the value was greater.
That's why we were doing the right century in an otherwise celestial tree.
So sorry, if I mixed those up for you right there and then we're turning the node down here just to
finish that off.
OK, so we did the client version and our private version.
Of this insert.
So let's see what else do we have to do?
We have the size and the in order.
So let's go ahead and do that.
Let's do the size, actually.
So I'm going to do science right here, I say, and BSG sighs.
We are doing the client version right now, so I'm going to say underscore size, which is our data
member, and I'm going to say call this function that passes the root and then return size to the user.
OK, let's make the other right inversion now.
So this is going to be science with the Trino node similar to the ones.
And then so I'm going to say, if node equals no point here, then return zero.
So you want to think about the case in which there is nothing in the tree.
So if it's just all initially, if Root is just null pointer, then we want to say that the size is
zero.
So that's why we're putting that as our base case.
Otherwise, what we are going to do is kind of an interesting recursive call that you may not have thought
about yet.
We are going to return and remember our return value as an ant, and we're going to kind of sum up the
nodes here.
So I'm going to say one.
Plus, the size of the current nodes, right century,
plus the size of the current nodes left Sochi, and so what this does is basically for each time that
we're coming through here and doing this recursive call, it's returning one.
It's adding one for all the nodes in the in any given knows right of and any given nodes left some tree
so you can think you we're using the integer one each time to represent each of the nodes that we would
have to see visually there.
And it's just basically talent in on another one every time it gets to a new node.
So that's how this size function is working with this recursive call here.
So kind of cool something new.
We're adding recursive calls together with an integer as well.
OK, so we have that out of the way.
Now let's go ahead and just do our in order traversal one, which is in order to dump.
So we're going to say boy GST in order dump.
And I'm just going to do the client one first, which all it really does is just call this other in
order.
And this one has two parts to it.
Now we're going to do our actual one that has most of the implementation testing route.
So we're going to do our base case.
It's going to be can you guess it?
The same thing, if known, is no point area since the voice function, we're just going to return.
And then what we're going to do, you probably know this already.
See if you can figure out yourself kind of our.
Got you a little close there, but see if you can pause the video and kind of guess what we're going
to do before I go ahead and cut it, because you're pretty familiar with this after the likes you.
OK, so what we're going to do is do in order dump, and then we will go to the left sub tree.
And then we're going to print it out in the middle
and damaged in line, and then we are going to do our in order dump of the right century.
OK, so that one should have been actually easy for you after the lecture.
It's pretty much the same exact thing that we saw there.
All right.
So now we kind of have all the functions I want to do right now, I don't I'm not going to do I don't
think I'm going to do the iterative find is that the other one we have?
Yeah, enter find.
I'm going to have another section, I think, where we go over iterative functions.
Well, we'll revisit this binary search tree and go over some iterative solutions to things.
A lot of them have to do with a different data structure that we haven't gone over yet.
And that's why ED Find would not have to use this new data structure I'm talking about, but a lot of
the other iterative ones do.
So what I'm going to do is wait until we discuss that data structure, and then we might just go ahead
and revisit the binary search tree and try and make use of that.
It's another data structure, and you just help us solve these recursive non recursive problems.
Iterative ones with the loops when we're trying to do another version and non recursive version of a
function or algorithm for a binary search tree.
Let's go ahead and do the main file now.
So I'm going to go over to main right now.
Going to get rid of this, and we already have a stream there, I'm going to make a file actually,
that we're going to use like a file stream object to take in our values to insert into the tree.
So include a stream.
And then of course, we want to include our header.
So I'm going to do that each.
And also this is trino dot h.
OK.
And do you sing in space?
Let's go ahead and put this in here, since we're taking it from a file again to our NRC for the number
of hours and then our charge star R&B array for arguments.
I'm going to do a little check here.
You know, like I can do this all the time to make sure that there is an argument being passed
to the file and you're running it.
So, you know, you put a little like a little usage error here to make sure the name of an input file.
OK.
And then you actually put these in brackets because I just want to say it with the FedEx Code after
this, so actually just going to do that.
OK, let's make an input file stream.
You can call it file in your file and open and whatever was passed as a command line argument.
And I'll make a new tree here.
I'm just going to call it tree.
And we'll say this new PSG, so that's just the default constructor, there are two integers so we can
go ahead and read in from the file and insert them right here and say, let's insert into the tree.
So while file in into our integer, I'm just going to say tree.
Actually, I don't know if I would do anything else in around with the brackets anyways, say tree insert.
And then I'm going to put three there.
So we'll just loop through and insert all the values from our file into our binary search tree.
OK.
Next time around and go ahead and just call all my functions to make sure that they work, let's do
them.
In order, though, what's the first thing we should do is make sure that our tree actually got all
the values inserted correctly and looks correct, so let's go ahead and do that in order to see if it
prints them in the correct orders.
That way, we know that our data structure is going to go.
So I'm going to say we're going to see out in order jump out of the tree and to allow cannot type today.
And then we will do Tree Arrows pointer in order downtown.
So that will be proof that we got our values in.
Let's go ahead and make a new file then.
When I say just new file, I'll just call this and put to you.
Let's go ahead and just do.
I don't know, one five eight three five.
No.
Yeah, five percent have repeated value, so we'll test that feature to make sure that the find was
working and wasn't doing repeated values there.
Uh, eleven and twenty three.
Let's just do that.
So it should print them out in order.
If our tree is all going to go and correct, we should see these printed out in order.
So it would be a way for us to confirm.
So I am going to go ahead and edit my configurations.
And let's do, in fact, 60.
Ford.
All right.
Try this again.
All right, there we go.
So I just needed to add that in there in order dump of three two three five eight 11 twenty three,
it looks like it printed in order.
So we're good to go there.
Sorry, I had to navigate through all my personal files there for a bit and just tried to actually find
that directory.
I guess it was because I didn't save it yet.
So apologies for that.
Get to see my messy.
Storage.
How have organized things?
Let's go ahead and do the next one then, so we will say we know that our find must be working well
with this go ahead and just like check that explicitly as well.
So enter a value to be found.
And I'm just going to say C into an EF four find, oh, I did not define that yet, actually.
So let me do that.
I need to make an integer, and then I will say if
tree find of F for fun, I will say it F.
And I'll just say found with curses.
Fine, I'm going to say that just because we might be doing it or find later.
OK, and then I'm also going to check my size, so I'm going to go ahead and say, I'm going to see
out the trees.
Size is.
And then we will see out tree size.
OK, so let's check this out as well.
We'll get the same in order to dump and then we should.
Get a it should ask us for a value to be found.
And then we'll enter that value and see if it's in our tree and then we can run again into something
else to kind of double check it and then we will get the tree size, which should be one two three four
five six seven.
So let's go ahead and run this.
OK, so enter a value to be found, let's say.
Yeah, we'll say Kate into.
Eight was found with recursive finesse as the trees size the seven, which is correct, should probably
put a little space there.
So let's go ahead and run this again and see if it finds something that's not in our trees.
I was going to say forty five, actually, let's see.
Let's say for your sake for.
So it didn't say the floor was found.
So that's good and says the chief scientist.
Seven.
All right, so we went over some kind of basic functions there.
Hopefully, there's recursive functions where easy enough for you to understand.
We're going to have some separate videos in the next part of this section where we're going to go over
some a little bit more difficult.
Functions, and I'm going to step through this in a very detailed manner with you.
I will also include an exercise for you to try out a new function that's like a little bit easier and
then we'll just go over the hard ones kind of in a video and step through them carefully so we can see
what they're doing.
Hopefully, you enjoyed this video and I will see you in the next one.