In this lecture we are going to go over implementing in our iterator for our binary search tree.
So like in previous lectures, we need to start off with creating our binary search tree iterator.
And this iterator obviously needs a lifetime.
And then our type where t implements the or trait and then our field in here is going to be a stack
for us to store our values.
And so we're just going to simply use a vector and then we will need our binary search tree of type
T.
And we want to get rid of that.
All right.
So that looks good.
So now we want to create an implementation block for our binary search tree iterator.
And then do the same thing where
TT implements the trait
and now we are good to go.
So we will say pub, F and Nuke so that we can create our new iterator.
We will have a tree being passed in which is going to be a reference to a binary search tree.
And then what we're going to return is a binary search tree iterator of type T.
So inside of our new method for our iterator, we will say Let a mutable editor is a binary search tree
iterator and now we want to initialize our stack.
So we'll use the macro and we will create it on the tree value that we pass in.
So what I want to do is actually create a helper function called Stack push left.
So we'll do that next.
And then from here we will return our iterator.
So our stack push left is going to be a helper function and it's going to contain a mutable reference
to our self.
And what we're going to do is say, while let some child is equal to a reference to our self stack dot
last dot unwrap dot left.
So we want to get the left value out of our child that is being passed in.
And when we do, we want to stack dot push.
That child.
So we're pushing that left value into our stack.
So what this is doing is it's getting all of the left values out of our tree.
And this is going to help us when we implement in our next method, which we can do right now.
And I'll be able to explain it all once it is set up that way.
It's just to make sure it's super clear on what we are doing.
So we're going to have our binary search tree iterator here where T implements board and then inside
of here we will have our type item which is of reference to our lifetime of type T, And now we have
our next method which contains a mutable reference to our self and returns an option.
So what we can do here is now say if self dot stack dot is empty,
then we can return none.
Otherwise we have some values that we can work with.
So we will say let node equals self, dot stack, dot pop dot unwrap.
So get the values from inside of what we just popped.
And then if node dot right is some meaning that there is a right value, then we want to self dot stack
dot push our node right as a reference dot, unwrap the value and then reference it that way we have
the actual value inside of it and then we want to push it.
Left self dot stack push left.
And now we want to return our node value as a ref.
So what we're doing here is and push left, stack, push left.
We are getting all the left values and pushing them onto loop onto our stack here.
When that left values on the stack, we're using that inside of our next value and we're checking to
see if that left value aka that node has some value also to the right of it.
So if that node has a right value and if it is, then we're going to push that onto our stack.
So what our iterator is doing is it's it's getting all the values from least to greatest in our iterator.
So when we iterate through our tree, we're always going to get the the least greatest value first,
and then the very last value that we iterate through will be our greatest value.
So our tree, when we iterate through it, will always be iterated from least to greatest, and we'll
be able to see that this holds true when we do our iterator test.
So the last thing that we need to do now is implement an.
Our iterator method in our binary search tree implementation block.
So this is going to return a new iterator which iterates over the tree in order from least to greatest.
And so it's going to be pub f and editor and self and it's going to return the iterator trait.
So input editor or item is equal to and reference to our t value.
And then very simply in here we will say we want a new binary tree iterator on our self.
So this is passing in our tree right here.
All right.
So all of this looks really good.
So let's implement in our test cases for our iterator to see how everything is looking.
And I renamed our create function here to create tree just to make have it make a little bit more sense.
So we have our test case and our test is going to be called test iterator.
So we have our tree equals create tree.
And now that we have our tree, we can say let mutable iterator equals tree.
Dot Editor So now we are creating our iterator for our tree and now we can start doing our assert equals.
So remember I said that we are going to have an iterator that goes from least to greatest in our tree
at all time.
So that would mean we'll go zero five, seven, 15, 27, 34 and 43.
So that is what I'm expecting our iterator to do down here.
So we'll go zero five, seven, 15, 27, 34 and 43.
So let's put all those in zero five, seven, 15, 27, 34 and 43 and then for our last one.
So now that we know that our iterator is at the end, we will say our editor next and we expect none
to be returned.
So everything I believe is good.
So let's run our test and see what we have.
We get an error saying no method named DX ref, so we need an import dx ref into our scope.
That's a very easy fix.
Thank you compiler.
So now if we run test again, we see that our test passes successfully.
So what our iterator is doing again, it is iterating the tree from excuse me, with values from least
to greatest.
So this would mean that our tree is going to be very easy to search for values for and searching is
the next implementation we will do and we will begin working on that in the next lecture.