1 00:00:06,710 --> 00:00:13,040 In this lecture we are going to go over implementing in our iterator for our binary search tree. 2 00:00:14,330 --> 00:00:22,220 So like in previous lectures, we need to start off with creating our binary search tree iterator. 3 00:00:22,430 --> 00:00:26,720 And this iterator obviously needs a lifetime. 4 00:00:27,800 --> 00:00:41,390 And then our type where t implements the or trait and then our field in here is going to be a stack 5 00:00:41,390 --> 00:00:44,810 for us to store our values. 6 00:00:44,810 --> 00:00:56,330 And so we're just going to simply use a vector and then we will need our binary search tree of type 7 00:00:56,360 --> 00:00:56,930 T. 8 00:00:59,740 --> 00:01:01,570 And we want to get rid of that. 9 00:01:03,790 --> 00:01:04,180 All right. 10 00:01:04,180 --> 00:01:05,260 So that looks good. 11 00:01:06,580 --> 00:01:14,710 So now we want to create an implementation block for our binary search tree iterator. 12 00:01:23,710 --> 00:01:26,920 And then do the same thing where 13 00:01:29,350 --> 00:01:32,560 TT implements the trait 14 00:01:34,960 --> 00:01:37,180 and now we are good to go. 15 00:01:37,180 --> 00:01:41,650 So we will say pub, F and Nuke so that we can create our new iterator. 16 00:01:41,650 --> 00:01:48,850 We will have a tree being passed in which is going to be a reference to a binary search tree. 17 00:01:50,080 --> 00:01:57,640 And then what we're going to return is a binary search tree iterator of type T. 18 00:01:59,170 --> 00:02:10,840 So inside of our new method for our iterator, we will say Let a mutable editor is a binary search tree 19 00:02:10,840 --> 00:02:14,800 iterator and now we want to initialize our stack. 20 00:02:15,040 --> 00:02:22,210 So we'll use the macro and we will create it on the tree value that we pass in. 21 00:02:23,590 --> 00:02:29,230 So what I want to do is actually create a helper function called Stack push left. 22 00:02:30,430 --> 00:02:31,900 So we'll do that next. 23 00:02:31,900 --> 00:02:35,290 And then from here we will return our iterator. 24 00:02:36,610 --> 00:02:45,100 So our stack push left is going to be a helper function and it's going to contain a mutable reference 25 00:02:45,100 --> 00:02:46,090 to our self. 26 00:02:47,170 --> 00:02:58,990 And what we're going to do is say, while let some child is equal to a reference to our self stack dot 27 00:02:59,080 --> 00:03:04,570 last dot unwrap dot left. 28 00:03:04,570 --> 00:03:11,410 So we want to get the left value out of our child that is being passed in. 29 00:03:11,410 --> 00:03:15,130 And when we do, we want to stack dot push. 30 00:03:17,310 --> 00:03:18,240 That child. 31 00:03:18,540 --> 00:03:23,350 So we're pushing that left value into our stack. 32 00:03:23,370 --> 00:03:28,200 So what this is doing is it's getting all of the left values out of our tree. 33 00:03:28,650 --> 00:03:38,820 And this is going to help us when we implement in our next method, which we can do right now. 34 00:03:38,820 --> 00:03:43,080 And I'll be able to explain it all once it is set up that way. 35 00:03:43,080 --> 00:03:47,670 It's just to make sure it's super clear on what we are doing. 36 00:03:48,300 --> 00:04:01,740 So we're going to have our binary search tree iterator here where T implements board and then inside 37 00:04:01,740 --> 00:04:12,210 of here we will have our type item which is of reference to our lifetime of type T, And now we have 38 00:04:12,210 --> 00:04:23,070 our next method which contains a mutable reference to our self and returns an option. 39 00:04:28,650 --> 00:04:36,360 So what we can do here is now say if self dot stack dot is empty, 40 00:04:41,490 --> 00:04:44,460 then we can return none. 41 00:04:46,710 --> 00:04:49,260 Otherwise we have some values that we can work with. 42 00:04:49,440 --> 00:04:57,930 So we will say let node equals self, dot stack, dot pop dot unwrap. 43 00:04:57,930 --> 00:05:02,070 So get the values from inside of what we just popped. 44 00:05:02,220 --> 00:05:15,930 And then if node dot right is some meaning that there is a right value, then we want to self dot stack 45 00:05:16,110 --> 00:05:31,230 dot push our node right as a reference dot, unwrap the value and then reference it that way we have 46 00:05:32,160 --> 00:05:35,580 the actual value inside of it and then we want to push it. 47 00:05:35,580 --> 00:05:39,720 Left self dot stack push left. 48 00:05:41,240 --> 00:05:46,520 And now we want to return our node value as a ref. 49 00:05:47,960 --> 00:05:53,270 So what we're doing here is and push left, stack, push left. 50 00:05:53,270 --> 00:05:58,460 We are getting all the left values and pushing them onto loop onto our stack here. 51 00:06:00,380 --> 00:06:07,010 When that left values on the stack, we're using that inside of our next value and we're checking to 52 00:06:07,010 --> 00:06:14,480 see if that left value aka that node has some value also to the right of it. 53 00:06:14,840 --> 00:06:20,030 So if that node has a right value and if it is, then we're going to push that onto our stack. 54 00:06:20,210 --> 00:06:27,830 So what our iterator is doing is it's it's getting all the values from least to greatest in our iterator. 55 00:06:27,830 --> 00:06:35,570 So when we iterate through our tree, we're always going to get the the least greatest value first, 56 00:06:35,570 --> 00:06:40,700 and then the very last value that we iterate through will be our greatest value. 57 00:06:40,700 --> 00:06:47,540 So our tree, when we iterate through it, will always be iterated from least to greatest, and we'll 58 00:06:47,540 --> 00:06:52,550 be able to see that this holds true when we do our iterator test. 59 00:06:52,880 --> 00:06:57,470 So the last thing that we need to do now is implement an. 60 00:06:58,640 --> 00:07:05,540 Our iterator method in our binary search tree implementation block. 61 00:07:06,020 --> 00:07:20,150 So this is going to return a new iterator which iterates over the tree in order from least to greatest. 62 00:07:20,600 --> 00:07:31,370 And so it's going to be pub f and editor and self and it's going to return the iterator trait. 63 00:07:31,370 --> 00:07:39,140 So input editor or item is equal to and reference to our t value. 64 00:07:39,680 --> 00:07:46,940 And then very simply in here we will say we want a new binary tree iterator on our self. 65 00:07:47,420 --> 00:07:50,150 So this is passing in our tree right here. 66 00:07:52,590 --> 00:07:52,920 All right. 67 00:07:52,920 --> 00:07:55,950 So all of this looks really good. 68 00:07:56,280 --> 00:08:05,580 So let's implement in our test cases for our iterator to see how everything is looking. 69 00:08:07,560 --> 00:08:16,830 And I renamed our create function here to create tree just to make have it make a little bit more sense. 70 00:08:18,480 --> 00:08:24,690 So we have our test case and our test is going to be called test iterator. 71 00:08:28,350 --> 00:08:33,180 So we have our tree equals create tree. 72 00:08:34,890 --> 00:08:42,120 And now that we have our tree, we can say let mutable iterator equals tree. 73 00:08:42,120 --> 00:08:49,080 Dot Editor So now we are creating our iterator for our tree and now we can start doing our assert equals. 74 00:08:49,680 --> 00:08:57,930 So remember I said that we are going to have an iterator that goes from least to greatest in our tree 75 00:08:57,930 --> 00:08:58,800 at all time. 76 00:08:59,310 --> 00:09:07,980 So that would mean we'll go zero five, seven, 15, 27, 34 and 43. 77 00:09:08,160 --> 00:09:12,150 So that is what I'm expecting our iterator to do down here. 78 00:09:12,150 --> 00:09:18,180 So we'll go zero five, seven, 15, 27, 34 and 43. 79 00:09:18,180 --> 00:09:37,170 So let's put all those in zero five, seven, 15, 27, 34 and 43 and then for our last one. 80 00:09:37,170 --> 00:09:44,880 So now that we know that our iterator is at the end, we will say our editor next and we expect none 81 00:09:44,880 --> 00:09:46,110 to be returned. 82 00:09:47,310 --> 00:09:49,470 So everything I believe is good. 83 00:09:49,470 --> 00:09:52,020 So let's run our test and see what we have. 84 00:09:52,020 --> 00:10:00,180 We get an error saying no method named DX ref, so we need an import dx ref into our scope. 85 00:10:00,180 --> 00:10:02,250 That's a very easy fix. 86 00:10:02,880 --> 00:10:04,320 Thank you compiler. 87 00:10:06,270 --> 00:10:11,970 So now if we run test again, we see that our test passes successfully. 88 00:10:12,240 --> 00:10:27,960 So what our iterator is doing again, it is iterating the tree from excuse me, with values from least 89 00:10:28,710 --> 00:10:29,790 to greatest. 90 00:10:30,090 --> 00:10:39,330 So this would mean that our tree is going to be very easy to search for values for and searching is 91 00:10:39,330 --> 00:10:46,500 the next implementation we will do and we will begin working on that in the next lecture.