1 00:00:02,830 --> 00:00:11,040 OK, so welcome to another lecture, and this lecture is going to be about binary search trees. 2 00:00:11,920 --> 00:00:19,150 So you probably noticed that we've already talked a little bit about a tree, at least, at least we've 3 00:00:19,150 --> 00:00:20,320 mentioned one. 4 00:00:20,770 --> 00:00:22,570 That was when we did the. 5 00:00:24,150 --> 00:00:30,630 Tree structure that represented the recursive calls, like, for example, when we looked at the Fibonacci 6 00:00:30,630 --> 00:00:41,670 sequence recursion problem, we also have a data structure that is like a tree as well that was kind 7 00:00:41,670 --> 00:00:47,370 of just a theoretical tree to help us visualize what the recursive calls look like. 8 00:00:47,940 --> 00:00:54,570 But trees are a popular part of computer science, and they are in fact, a data structure similar to 9 00:00:54,570 --> 00:00:55,560 what you see here. 10 00:00:56,550 --> 00:00:59,640 So let's go ahead and talk about these binary search trees. 11 00:01:02,000 --> 00:01:08,990 OK, so we have binary trees, and then more specifically, binary search tree is a binary tree is technically 12 00:01:08,990 --> 00:01:17,570 just a collection of nodes that start at a root node, which should be right here and they can have 13 00:01:17,570 --> 00:01:24,650 up to don't have to be we can have up to two children, so zero to two children, which would be a left 14 00:01:24,650 --> 00:01:26,810 and a right child if you had two children. 15 00:01:27,780 --> 00:01:31,490 Let's look at some more specific rules about binary search trees. 16 00:01:32,840 --> 00:01:39,920 Each note of the binary search tree, like I said, can have a zero one or two children for each node 17 00:01:40,550 --> 00:01:48,270 on nodes, and that nodes less of tree have to have a value that is less than or equal to X. 18 00:01:48,270 --> 00:01:54,170 So you see here, when we're talking about a Node X, this value in it's left. 19 00:01:54,170 --> 00:01:56,720 Some tree has to be less than or equal to it. 20 00:01:56,720 --> 00:02:04,610 So if we're talking about ten here and we see seven, that is less than 10 for each Node X, all nodes 21 00:02:04,610 --> 00:02:08,720 in the right sub tree have a value greater than or equal to X. 22 00:02:08,720 --> 00:02:16,160 So we talked about the left Sochi being left at less the right seven tree coming off a given Node X 23 00:02:16,190 --> 00:02:19,750 has to be greater than or equal to. 24 00:02:19,760 --> 00:02:21,590 So we see that this is greater than as well. 25 00:02:21,590 --> 00:02:25,730 And if you check out the rest of the tree, you'll notice that these rules are upheld. 26 00:02:27,470 --> 00:02:31,790 Both the left and right symmetries of X must also be binary surgery. 27 00:02:31,800 --> 00:02:39,650 So pretty much what that saying is that if we're let's say we're at this route node here, if we go 28 00:02:39,650 --> 00:02:44,690 over here and we like, if we look, if we lift this root node and we're talking about this whole thing 29 00:02:44,690 --> 00:02:50,960 as being a binary search tree, and then we go down to here to seven and then we just looked at this 30 00:02:50,960 --> 00:02:55,270 whole sub tree here that was coming off this connection. 31 00:02:55,280 --> 00:02:58,310 This all has to be a binary search tree as well. 32 00:02:58,340 --> 00:02:59,330 Same for everything. 33 00:02:59,330 --> 00:03:02,270 Like I go here, this whole tree has to be binary search tree. 34 00:03:02,510 --> 00:03:04,520 This whole tree has to be binary surgery. 35 00:03:07,130 --> 00:03:14,000 So as long as those rules are upheld, then we have a binary search tree. 36 00:03:16,720 --> 00:03:25,720 So let's go ahead and walk through an example of inserting some numbers into this binary search tree. 37 00:03:26,650 --> 00:03:27,640 So I have a list of numbers. 38 00:03:27,640 --> 00:03:29,830 I'm starting from left to right and inserting them. 39 00:03:31,480 --> 00:03:34,550 So we start out with 10 that becomes our root node. 40 00:03:34,570 --> 00:03:38,710 So the first thing that you have that you're inserting will be the root node. 41 00:03:40,790 --> 00:03:43,410 Then we have 18, that's greater than 10. 42 00:03:43,610 --> 00:03:46,820 So we branch off to the right and put it to the right of 10. 43 00:03:48,770 --> 00:03:50,720 We have seven, which is less than 10. 44 00:03:51,320 --> 00:03:55,640 So we range off to the left, so you can imagine seven came in here. 45 00:03:56,270 --> 00:03:57,960 We compared it to 10. 46 00:03:57,980 --> 00:04:00,150 We said, OK, seven is less than 10. 47 00:04:00,170 --> 00:04:01,070 So we put it here. 48 00:04:03,200 --> 00:04:05,490 We have twenty one, so twenty one goes here. 49 00:04:06,260 --> 00:04:09,910 We said twenty one is greater than ten is twenty one greater than eighteen. 50 00:04:09,920 --> 00:04:10,450 Yes, it is. 51 00:04:10,460 --> 00:04:13,280 So we'll make that the right child of eighteen. 52 00:04:15,030 --> 00:04:17,310 Then we have five, let's go ahead and think about that. 53 00:04:17,340 --> 00:04:19,620 Five comes in to 10. 54 00:04:20,100 --> 00:04:21,270 It's less than 10. 55 00:04:21,570 --> 00:04:22,920 We compare it to seven. 56 00:04:23,370 --> 00:04:26,340 It's less than seven, so it should be right here. 57 00:04:28,020 --> 00:04:34,030 There it is, and then we have three, three years compared to 10, then we it's less than 10. 58 00:04:34,030 --> 00:04:36,730 So we come here, we say it's three less than seven. 59 00:04:37,600 --> 00:04:38,330 Yes, it is. 60 00:04:38,860 --> 00:04:40,720 It's three less than five. 61 00:04:40,750 --> 00:04:41,470 Yes, it is. 62 00:04:41,620 --> 00:04:42,550 So we put that here. 63 00:04:43,630 --> 00:04:44,050 Eight. 64 00:04:44,980 --> 00:04:48,940 It is less than 10, and we get here is eight less than seven, no. 65 00:04:49,360 --> 00:04:51,010 It's a greater than seven, yes. 66 00:04:51,010 --> 00:04:52,180 So we put it right here. 67 00:04:53,860 --> 00:05:01,570 Sex comes in, sex is less than 10, sex is less than seven, sex is not less than five is greater than 68 00:05:01,570 --> 00:05:03,280 five, so we're going to put sex right here. 69 00:05:05,990 --> 00:05:08,720 Nine comes in, nine is less than 10. 70 00:05:08,930 --> 00:05:13,580 Nine is greater than seven, and nine is greater than eight. 71 00:05:13,940 --> 00:05:15,320 So we're going for that right here. 72 00:05:16,710 --> 00:05:21,270 Twelve thousand year, twelve is greater than ten, but it's less than 18. 73 00:05:21,540 --> 00:05:25,350 So we put that here and then finally, 29 is greater than 10. 74 00:05:25,360 --> 00:05:27,570 It's great in the 18 and it's getting twenty one. 75 00:05:27,570 --> 00:05:28,500 So we put that here. 76 00:05:30,300 --> 00:05:35,280 So basically, as the values come in, they just kind of trickle down the tree until they find their 77 00:05:35,280 --> 00:05:36,720 respective spots. 78 00:05:36,720 --> 00:05:42,750 So at each given node, you're asking less than or greater, then it's less than to the left greater 79 00:05:42,750 --> 00:05:43,470 than to the right. 80 00:05:43,470 --> 00:05:47,280 And you kind of build your tree downward like this to different branches. 81 00:05:49,110 --> 00:05:51,180 OK, so let's continue on. 82 00:05:52,530 --> 00:05:56,200 So what are these binary tree searches good for? 83 00:05:56,220 --> 00:05:57,180 What can we use them for? 84 00:05:57,210 --> 00:05:59,070 Why are they an important data structure? 85 00:06:00,140 --> 00:06:05,660 Well, they're called binary search trees for a reason, and that's because they can make searching 86 00:06:05,660 --> 00:06:13,010 a lot faster because of the way the tree is organized, so you might have already heard of the binary 87 00:06:13,010 --> 00:06:19,010 search algorithm, or you would use that on an array or vector or something. 88 00:06:19,580 --> 00:06:28,940 And you might have remembered if anyone had mentioned that the time complexity of that was log based 89 00:06:28,940 --> 00:06:32,660 to an end so show of log in. 90 00:06:34,180 --> 00:06:40,750 We have a similar situation with this binary search tree for searching for a number in here. 91 00:06:41,050 --> 00:06:42,190 So let's take a look at that. 92 00:06:43,690 --> 00:06:50,650 If we take a look at this tree, we can make some observations about the time taken to search for whatever 93 00:06:50,650 --> 00:06:56,260 value we're looking at while looking at the relationship of the number of nodes and the height of the 94 00:06:56,260 --> 00:06:56,980 tree. 95 00:06:57,880 --> 00:06:59,750 So how many notice do we have? 96 00:06:59,770 --> 00:07:03,820 One two three four five six seven. 97 00:07:04,270 --> 00:07:06,730 And our height is one two. 98 00:07:08,840 --> 00:07:15,830 So what we can actually say for a binary search tree like this, this is actually a perfect tree. 99 00:07:16,820 --> 00:07:22,910 So that means a perfect tree is basically when it is perfectly balanced like this. 100 00:07:22,910 --> 00:07:24,950 Like you notice that there is three. 101 00:07:25,130 --> 00:07:28,760 There's like this exact sub tree is repeated over here and it is over here. 102 00:07:31,520 --> 00:07:43,670 And when we're looking at the height compared to the nose of this, we can say that the height of the 103 00:07:43,910 --> 00:07:53,150 tree or the number of nodes of the tree would be two to the height plus one power minus one. 104 00:07:53,570 --> 00:07:56,000 So we have a height of one two. 105 00:07:57,350 --> 00:08:05,600 And so if we do two to the two plus one, that is two to the third power that is eight and eight minus 106 00:08:05,600 --> 00:08:06,770 one is seven. 107 00:08:06,770 --> 00:08:11,150 And we notice that we have one two three four five six seven nodes. 108 00:08:12,830 --> 00:08:18,950 And we haven't gotten into a detailed algorithm analysis yet, but I keep hinting that we are going 109 00:08:18,950 --> 00:08:20,000 to go over that in the future. 110 00:08:20,000 --> 00:08:31,250 But if you were to analyze that in a more poufy kind of manner, you would notice that the time taken 111 00:08:31,250 --> 00:08:39,110 to search or insert is actually log base to end because the tree is like this. 112 00:08:40,460 --> 00:08:46,760 So the that's why we have here at the time, taking the specific tree is a log in because the height 113 00:08:46,760 --> 00:08:47,380 is long. 114 00:08:47,390 --> 00:08:56,570 And if you were to look at that to to the height plus one power minus one and kind of solve that, mathematically 115 00:08:56,570 --> 00:08:57,380 you could see that. 116 00:08:58,340 --> 00:09:05,630 And that, of course, is where we're considering and to be the size of the input, which is also the 117 00:09:05,630 --> 00:09:06,410 number of nodes. 118 00:09:08,570 --> 00:09:18,350 So it is oh big oh of log in for the best case and average case time complexity for both insertion and 119 00:09:18,350 --> 00:09:21,050 search operations in the binary search tree. 120 00:09:24,190 --> 00:09:32,830 But what about the worst case then we talked about it being Lord big of log in for the average and best 121 00:09:32,830 --> 00:09:33,340 case. 122 00:09:34,680 --> 00:09:43,200 Well, think about what would happen if we built a tree by using our input like we did before, but 123 00:09:43,200 --> 00:09:46,740 our input was coming in an ascending order. 124 00:09:48,360 --> 00:09:49,670 Or descending order? 125 00:09:50,160 --> 00:09:53,430 So, yeah, right here in this example, we have a descending order. 126 00:09:54,120 --> 00:09:55,250 So what would that look like? 127 00:09:55,260 --> 00:09:59,760 Think about that for a second, maybe pass the video and see if you could draw that out on paper before 128 00:09:59,760 --> 00:10:00,960 I go over it right here. 129 00:10:02,990 --> 00:10:07,910 OK, so if you did draw that on paper and let's see if you got something similar. 130 00:10:09,050 --> 00:10:13,760 So we start out with 10, eight comes in, it's less than 10. 131 00:10:14,420 --> 00:10:21,310 We do a less surgery, then we have seven coming in seven, six and 10 of us and eight. 132 00:10:21,320 --> 00:10:22,310 So we put it right here. 133 00:10:22,580 --> 00:10:25,490 Five coming in five or six in 10 five is less than that. 134 00:10:25,490 --> 00:10:26,780 Five is less than seven. 135 00:10:27,290 --> 00:10:28,370 We put that here. 136 00:10:29,580 --> 00:10:35,280 We could keep going, and if you ended and if this were still in descending order, but you can kind 137 00:10:35,280 --> 00:10:36,840 of see a trend here. 138 00:10:39,830 --> 00:10:46,340 So do you notice anything familiar about the way this binary search tree looks? 139 00:10:47,010 --> 00:10:49,790 Think about data structures that we've already gone over. 140 00:10:51,890 --> 00:11:00,650 So you might be saying, hey, this kind of looks like a singly linked list and basically is and the 141 00:11:00,650 --> 00:11:07,700 problem with this is if we have it in this order, that means that searching for something becomes similar 142 00:11:07,700 --> 00:11:12,500 to how we would need to search for something in a linked list. 143 00:11:13,190 --> 00:11:18,170 And instead, we have to pretty much do like a sequential search at this point, which is going to be 144 00:11:18,170 --> 00:11:19,220 linear time. 145 00:11:19,220 --> 00:11:23,090 And so it's going to be big of in instead of of log in. 146 00:11:23,510 --> 00:11:33,500 So the worst case to search and insert as well is going to be big go of in linear time for binary search 147 00:11:33,500 --> 00:11:33,830 tree. 148 00:11:38,800 --> 00:11:47,980 OK, so let's go ahead and think about how to traverse this binary search tree data structure and what 149 00:11:47,980 --> 00:11:55,360 we're going to do is put this new concept that we just learned recursion to use to traverse this tree 150 00:11:55,360 --> 00:11:56,740 in a few different ways. 151 00:11:57,610 --> 00:12:02,320 We're going to cover three major types of reversals in this lecture. 152 00:12:03,900 --> 00:12:07,650 And it's going to be in the context of printing all the values in the tree. 153 00:12:08,880 --> 00:12:11,790 And so I have some I have these three listed here. 154 00:12:12,210 --> 00:12:18,690 When you see the word current that is so synonymous with us printing the value in the tree, so I'm 155 00:12:18,690 --> 00:12:22,620 saying print something, print the data at the current node. 156 00:12:22,890 --> 00:12:27,360 Think of it like a linked list node and you had that data member. 157 00:12:28,560 --> 00:12:34,470 We're going to go ahead and print that data member at the node so you can compare it to what we've done 158 00:12:34,470 --> 00:12:35,910 with link lists so far. 159 00:12:36,750 --> 00:12:40,660 And then the left and the right are, of course, respectively. 160 00:12:40,730 --> 00:12:45,450 You know, here in here, like going to the left cemetery in the cemetery. 161 00:12:46,930 --> 00:12:52,240 Just talking about the what we're doing and what order we're doing things, so, you know, this is 162 00:12:52,240 --> 00:13:02,170 like print the current value, then take a left, then take a right in order traversal would be take 163 00:13:02,170 --> 00:13:02,770 a left. 164 00:13:03,040 --> 00:13:04,420 Print the current value. 165 00:13:04,420 --> 00:13:06,580 Take a write post. 166 00:13:06,580 --> 00:13:10,390 Order would be take a left, take a right and then print the current value. 167 00:13:10,390 --> 00:13:11,950 So that's what I'm talking about here. 168 00:13:14,790 --> 00:13:26,820 OK, so I'm going to do a major like slow walk through all, go over all the details and kind of walk 169 00:13:26,820 --> 00:13:33,300 through of this pre order traversal algorithm just so we can get really good understanding of what's 170 00:13:33,300 --> 00:13:42,090 going on with these recursive algorithms to traverse the tree in the next to the in order and post order. 171 00:13:42,420 --> 00:13:48,630 I'm going to kind of just go over those in a little less detail, so I'm not going to, like, show 172 00:13:48,630 --> 00:13:51,100 each line executing and what's happening. 173 00:13:51,240 --> 00:13:56,340 I'm just kind of kind of show what order the nodes are going to be printed in and just step through 174 00:13:56,340 --> 00:13:56,910 it that way. 175 00:13:58,110 --> 00:13:59,450 So let's go ahead and start. 176 00:13:59,460 --> 00:14:01,500 We're starting out at the root node. 177 00:14:02,130 --> 00:14:08,100 You see that this node is being passed here, so you can imagine that this node gets passed here. 178 00:14:08,280 --> 00:14:10,240 And then we start this function. 179 00:14:10,270 --> 00:14:13,260 We start this preorder traversal algorithm. 180 00:14:15,140 --> 00:14:17,330 So what we're seeing is the no no. 181 00:14:17,630 --> 00:14:21,170 If it is returned the notice, not no, we're all good here. 182 00:14:21,170 --> 00:14:22,220 This is not a no. 183 00:14:24,600 --> 00:14:28,290 OK, so then we come right here. 184 00:14:28,830 --> 00:14:29,860 The note is not null. 185 00:14:29,880 --> 00:14:33,570 We're going to go ahead and print out our data here, which is 10. 186 00:14:36,210 --> 00:14:43,080 Then we're going to hit this line here, and we're going to recursively call the function and pass the 187 00:14:43,090 --> 00:14:46,500 nodes, the current nodes left some tree, so we're on this node. 188 00:14:46,740 --> 00:14:51,750 We're going to pass it the last century, which is going to lead us to this node. 189 00:14:51,750 --> 00:14:56,550 So this is the node that we are passing to our function recursively now. 190 00:14:59,250 --> 00:15:02,430 So now we're on here, you see the green arrow denoting where we are. 191 00:15:02,790 --> 00:15:06,540 If the note is null, then return the notice, not null. 192 00:15:08,250 --> 00:15:12,060 We're going to go ahead and print out the value at this node. 193 00:15:13,310 --> 00:15:15,680 Let's do another recursive call with the left sub tree. 194 00:15:16,920 --> 00:15:19,380 So now we're here the nodes, not no. 195 00:15:19,620 --> 00:15:20,790 We're going to print that out. 196 00:15:22,100 --> 00:15:24,050 Another recursive call with the left sub tree. 197 00:15:25,700 --> 00:15:26,630 So now we're here. 198 00:15:28,550 --> 00:15:31,580 It's not north, so we printed out the native value there three. 199 00:15:33,710 --> 00:15:34,140 OK. 200 00:15:34,730 --> 00:15:36,320 Let's go to the next one. 201 00:15:36,350 --> 00:15:39,830 Another recursive call, we're going to pass the left sub tree. 202 00:15:41,400 --> 00:15:44,910 But you notice that we have a red arrow there, and it's pointing to no. 203 00:15:45,000 --> 00:15:50,220 So similar to the linked lists at the end of the linked list coming off the tail, remember we had a 204 00:15:50,220 --> 00:15:55,410 null pointer, so it's going to be similar here in the tree with three in this specific example has 205 00:15:55,410 --> 00:16:00,780 a no pointer for the left side tree and for the rates of tree, so it's pointing to null. 206 00:16:00,780 --> 00:16:01,560 It is null. 207 00:16:01,560 --> 00:16:05,700 So we hit that line and it says return and we return and we go back. 208 00:16:06,680 --> 00:16:12,560 We came to it back to where we were, we came from that print pre-order, no less arbitrary call. 209 00:16:12,860 --> 00:16:19,640 Now we go down one line since we returned to that last February call and is saying recursively, call 210 00:16:19,640 --> 00:16:20,480 it right century. 211 00:16:21,750 --> 00:16:27,150 We already said and mentioned that the cemetery is also known as an old player. 212 00:16:28,260 --> 00:16:31,110 So we're going to return and we're coming back. 213 00:16:32,910 --> 00:16:35,190 We're going to go back up now to the five. 214 00:16:38,210 --> 00:16:40,310 And we've already explored the left. 215 00:16:40,910 --> 00:16:47,390 So we're going one line down and we're going to explore the right, so recursively call that now we're 216 00:16:47,390 --> 00:16:48,290 at six, it's not. 217 00:16:48,290 --> 00:16:48,710 No. 218 00:16:49,010 --> 00:16:50,420 So we're going to print out the data. 219 00:16:52,380 --> 00:16:58,140 We're going to take left cemetery, but it is a leaf node, like we mentioned out before, I called 220 00:16:58,140 --> 00:17:00,270 those leaf nodes in the recursive tree. 221 00:17:00,300 --> 00:17:02,630 We're going to use that terminology here as well. 222 00:17:02,640 --> 00:17:03,060 These. 223 00:17:03,490 --> 00:17:04,140 This is a leaf. 224 00:17:04,150 --> 00:17:05,250 No, this is a leaf node. 225 00:17:05,280 --> 00:17:09,430 This is a leaf node and this is the leaf node because they are at the bottom and they just have these 226 00:17:09,450 --> 00:17:10,740 node pointers coming out of them. 227 00:17:12,440 --> 00:17:15,470 OK, so that is all so we return back. 228 00:17:17,050 --> 00:17:19,110 Then we say, hey, let's check out the right subject. 229 00:17:20,080 --> 00:17:20,860 That is no. 230 00:17:21,700 --> 00:17:27,970 So we return and now we return all the way back up here because we've already explored all these left 231 00:17:27,970 --> 00:17:29,490 and right and printed out stuff. 232 00:17:29,500 --> 00:17:33,250 So now we're coming all the way back up our stack frames to here. 233 00:17:36,730 --> 00:17:38,650 OK, so we're on seven. 234 00:17:40,470 --> 00:17:43,800 We already explored less of trees, so we're going down the right sub tree. 235 00:17:43,950 --> 00:17:47,280 We recursively call that that moves us to eight. 236 00:17:48,790 --> 00:17:50,740 It's not no, we're going to go ahead and print that out. 237 00:17:51,280 --> 00:17:53,260 We're going to check out the left, some tree. 238 00:17:54,340 --> 00:17:55,820 Oh, left, some tree is no. 239 00:17:55,840 --> 00:17:57,880 So let's return and we go back to eight. 240 00:17:59,700 --> 00:18:01,710 Now we're going down right, sub three. 241 00:18:03,340 --> 00:18:04,450 Some trees, not no. 242 00:18:04,480 --> 00:18:05,560 So let's print that out. 243 00:18:06,670 --> 00:18:10,600 So less of a tree, there's a leaf node, so it's now your turn back. 244 00:18:10,930 --> 00:18:11,230 Right? 245 00:18:11,230 --> 00:18:18,580 Some tree also know we're going to return back and now we've already explored the left and right all 246 00:18:18,580 --> 00:18:20,020 the way down for this seven node. 247 00:18:20,020 --> 00:18:22,660 So now we're coming back up to the root node here. 248 00:18:24,340 --> 00:18:25,960 So we've already explored the left. 249 00:18:25,960 --> 00:18:28,150 You notice we came back here to this last century. 250 00:18:28,150 --> 00:18:31,240 We're returning back to this point in time where we've already called this. 251 00:18:32,170 --> 00:18:34,150 So now we're going to go explore the right. 252 00:18:34,420 --> 00:18:35,980 So we hit the right, some tree. 253 00:18:38,160 --> 00:18:42,690 Now we are at 18, and it's not, no, so it's apparent that. 254 00:18:43,680 --> 00:18:47,670 Let's check out the left Sochi, we go to 12, it's not know we're going to print that out. 255 00:18:48,750 --> 00:18:52,260 Now we're at Alief, so that's going to be no. 256 00:18:52,800 --> 00:18:55,020 So we're going to come back, we're going to look to the right. 257 00:18:55,030 --> 00:18:56,070 That's also no. 258 00:18:56,730 --> 00:18:58,500 So we're coming back up to this node. 259 00:19:00,160 --> 00:19:02,170 And then we look at the right sub tree. 260 00:19:02,980 --> 00:19:03,790 That is Noel. 261 00:19:04,840 --> 00:19:09,610 And then we're pretty much done because it came back to the recreation of here and we printed everything 262 00:19:09,610 --> 00:19:11,320 in our pre order traversal. 263 00:19:14,160 --> 00:19:19,380 OK, so hopefully that was detailed enough for you to kind of understand how we go through the tree 264 00:19:19,380 --> 00:19:20,310 with recursion. 265 00:19:21,000 --> 00:19:22,800 Let's go ahead and check out the next one. 266 00:19:22,980 --> 00:19:27,150 So this time I'm not going to step through with detailed, but we're just going to talk about in what 267 00:19:27,150 --> 00:19:28,470 order the nodes print. 268 00:19:28,980 --> 00:19:32,040 So you notice now we're doing in order to rehearsal. 269 00:19:32,040 --> 00:19:32,870 So we have house. 270 00:19:32,880 --> 00:19:34,590 I wrote a note here, just like before. 271 00:19:35,310 --> 00:19:41,880 But what we are doing is we're doing a less arbitrary recursive call and then we are printing our data 272 00:19:41,880 --> 00:19:44,190 in the middle and then we are doing a right summary call. 273 00:19:46,540 --> 00:19:50,980 So I'm just going to step through it because it's just going to tell us what the the green arrow will 274 00:19:50,980 --> 00:19:54,640 denote, what is getting printed first and what order. 275 00:19:56,480 --> 00:19:57,680 So we start here. 276 00:19:58,440 --> 00:20:02,660 We're going to have it's not no, so we're going to have a left Sochi call, so it's going to go here. 277 00:20:03,470 --> 00:20:06,130 This is not normal, so it's going to have another massive recall. 278 00:20:06,140 --> 00:20:07,220 This is the first thing. 279 00:20:07,220 --> 00:20:13,280 So we're just going to keep taking left, so left, left left and then we're going to go all the way 280 00:20:13,280 --> 00:20:16,580 down and it's going to be null and then we're going to come back. 281 00:20:17,610 --> 00:20:21,750 And then once we return back to here, we'll be going to this line. 282 00:20:22,750 --> 00:20:27,550 And we will print out our data, so we'll be printing out three. 283 00:20:27,820 --> 00:20:36,040 And you notice that I am not having that there, but then what we do at that point is we are doing our 284 00:20:36,040 --> 00:20:37,000 right obituary. 285 00:20:37,330 --> 00:20:40,750 So sorry, I kind of jumped ahead there, but we print our data. 286 00:20:40,750 --> 00:20:43,900 We do the right century right of trees and also we return back. 287 00:20:46,400 --> 00:20:51,290 And we're going to return all the way back to here, and we already checked out the left cemetery for 288 00:20:51,290 --> 00:20:56,630 here, so we would go down to the next line and we would print out the data here. 289 00:20:56,720 --> 00:20:59,160 So that's what this is for and saying now we're printing five. 290 00:20:59,180 --> 00:20:59,960 That's where we're at. 291 00:21:00,590 --> 00:21:02,240 Then we're going to check the right cemetery. 292 00:21:02,990 --> 00:21:05,120 So we go down to the right cemetery. 293 00:21:06,170 --> 00:21:07,850 And so that gets passed up here. 294 00:21:08,780 --> 00:21:09,800 And then where? 295 00:21:09,800 --> 00:21:10,600 So we're right here. 296 00:21:10,850 --> 00:21:13,490 And then we hit the left cemetery recursive call. 297 00:21:13,490 --> 00:21:14,810 So we would check out left. 298 00:21:14,820 --> 00:21:16,640 Oh, it's no we would come back. 299 00:21:17,210 --> 00:21:22,310 Since we came back from this left cemetery, we go to the next line and we would print out the data 300 00:21:22,310 --> 00:21:22,610 here. 301 00:21:25,920 --> 00:21:28,950 OK, and then we would check out the rates of tree would be no. 302 00:21:28,980 --> 00:21:36,420 We'd come back and return all the way back up to here to this seven and then we said we'd be right here 303 00:21:36,420 --> 00:21:41,310 and then we come down and we would print our seven right here. 304 00:21:43,460 --> 00:21:47,600 Then we would hit the right cemetery of seven that hasn't been explored yet. 305 00:21:47,930 --> 00:21:49,490 It would bring us down to here. 306 00:21:49,490 --> 00:21:51,140 We had the left cemetery it is now. 307 00:21:51,140 --> 00:21:53,090 When we come back, we'd print the note. 308 00:21:54,710 --> 00:21:57,160 Once we printed the known, we check out Right Cemetery. 309 00:21:57,200 --> 00:21:58,910 We'd be at nine. 310 00:21:59,090 --> 00:22:03,110 Check out Left Cemetery, it's no we'd come back and then we'd print out. 311 00:22:04,250 --> 00:22:05,750 This right here, the nine. 312 00:22:07,180 --> 00:22:08,750 We explore Nine's right century. 313 00:22:08,770 --> 00:22:11,680 It's a leaf, so there'll be no when we come back here. 314 00:22:12,850 --> 00:22:15,830 After explaining, right, some, we go all the way back up. 315 00:22:15,850 --> 00:22:18,250 We've already explored all these, so we go back to the root. 316 00:22:19,780 --> 00:22:24,700 The real Arctic's for the left, so we come back to here, we go to this line. 317 00:22:25,810 --> 00:22:29,950 So you notice that I'm coming back, you know, when I say we come back to here, we're going back to 318 00:22:29,950 --> 00:22:31,250 those previous stack frames. 319 00:22:31,270 --> 00:22:32,110 That's what I'm talking about. 320 00:22:32,830 --> 00:22:35,530 So we go ahead and print out 10, which is our route node. 321 00:22:36,550 --> 00:22:38,350 Then we even head up to right some tree. 322 00:22:38,920 --> 00:22:39,810 We go over here. 323 00:22:39,820 --> 00:22:41,440 Sorry, I click too early again. 324 00:22:42,880 --> 00:22:43,430 We do the right. 325 00:22:43,430 --> 00:22:44,020 Some tree. 326 00:22:45,400 --> 00:22:48,580 Then we would do this left some call. 327 00:22:51,340 --> 00:23:01,480 And it would be 12, so we would print out 12, then we would do the right sub tree, then we would 328 00:23:01,480 --> 00:23:02,740 do the less arbitrary. 329 00:23:03,700 --> 00:23:04,690 We would come back up. 330 00:23:05,050 --> 00:23:06,910 18 would be the next thing printed. 331 00:23:07,180 --> 00:23:10,300 And now we've printed all of the nodes in the tree. 332 00:23:11,590 --> 00:23:13,180 So that is an order traversal. 333 00:23:15,090 --> 00:23:20,670 Now, let's check out post order traversal that's going to be left, then right, then print the current 334 00:23:20,670 --> 00:23:20,940 note. 335 00:23:22,340 --> 00:23:27,770 Same thing we started out now we do in both recursive calls before printing, so it's can do the same 336 00:23:27,770 --> 00:23:31,820 thing where it does left first, so it's going to go all the way down left. 337 00:23:32,600 --> 00:23:38,390 So we're going all the way down here and it's going to hit nil and it's going to come back here and 338 00:23:38,390 --> 00:23:44,180 then it's going to do right and then it's going to come back and then it's going to print the data. 339 00:23:48,480 --> 00:23:55,860 After that, it's going to come back up to here and it's going to go right because we're coming back 340 00:23:55,860 --> 00:23:56,610 to this left. 341 00:23:57,590 --> 00:23:58,730 And it's going to go right. 342 00:23:59,150 --> 00:24:02,870 And once we do, the rates of tree. 343 00:24:04,870 --> 00:24:05,350 Call. 344 00:24:07,910 --> 00:24:10,340 Then let's see who we'd be on five. 345 00:24:10,640 --> 00:24:15,500 It would do the right surgical and then it would print out the notes data. 346 00:24:17,600 --> 00:24:19,730 Then it would come back. 347 00:24:20,820 --> 00:24:24,000 And then we have already done left and right for five. 348 00:24:24,030 --> 00:24:26,430 So it would print five data. 349 00:24:29,560 --> 00:24:36,010 OK, so then we would come back and we go all the way down here because we've already explored all the 350 00:24:36,010 --> 00:24:40,270 left of seven, we're going to do the right cemetery cause we're going to go all the way down here. 351 00:24:40,660 --> 00:24:44,440 And once we've gone down all the way on the right centuries, we have our data afterwards. 352 00:24:44,440 --> 00:24:45,460 So we'd print that. 353 00:24:49,330 --> 00:24:54,310 And then we're coming back and we're printing this because we're recursively coming back, we've already 354 00:24:54,310 --> 00:24:55,840 done the left. 355 00:24:56,260 --> 00:25:02,440 We would actually do to the left of this and then, yeah, so that's already printed out. 356 00:25:04,230 --> 00:25:05,340 Then when you do seven. 357 00:25:07,690 --> 00:25:12,730 Coming all the way down and we've explored the left from the root, so now we're going to have to come 358 00:25:12,730 --> 00:25:16,510 down here to the right and then we have our left some free call first. 359 00:25:16,900 --> 00:25:21,280 So we're going to hit this up first and then we'll come back and hit this up. 360 00:25:21,280 --> 00:25:23,470 And then finally, it will print the root node. 361 00:25:26,320 --> 00:25:27,940 So hopefully that makes sense for you. 362 00:25:28,330 --> 00:25:33,880 And then step through in as much detail, but you can kind of get the gist after looking at that first 363 00:25:33,880 --> 00:25:41,440 one is kind of where we place this print in relation to our left and right submarine cars. 364 00:25:42,730 --> 00:25:44,910 So they're useful for different things. 365 00:25:44,920 --> 00:25:49,630 Sometimes if you have trees that are holding like mathematical expressions, this post order can be 366 00:25:50,140 --> 00:25:53,890 a nice thing to be used to print it in a certain way. 367 00:25:54,790 --> 00:26:00,400 Most of the time, though, we're going to care about in order traversal because we want to print these 368 00:26:00,400 --> 00:26:02,590 values in their sort in order. 369 00:26:02,860 --> 00:26:07,450 So that is something that we will be implementing in code. 370 00:26:07,450 --> 00:26:14,140 You already saw an implementation here, but we're going to go ahead and write that in code as well, 371 00:26:14,140 --> 00:26:16,540 and we'll do some other recursive functions. 372 00:26:18,150 --> 00:26:18,630 As well. 373 00:26:20,400 --> 00:26:24,420 OK, so that is actually all I have for this lecture. 374 00:26:25,050 --> 00:26:34,530 We're going to get right into writing some code for this binary search tree and we will look at 13 functions 375 00:26:34,530 --> 00:26:38,730 and a few other things we might get into deleting as well. 376 00:26:38,740 --> 00:26:42,060 But hopefully it gave you a decent overview of the binary search tree. 377 00:26:42,330 --> 00:26:53,490 There are multiple types of trees, and they don't all necessarily have to be made up of like pointers 378 00:26:53,580 --> 00:26:59,550 like a link list like pointers and knows some of them can be implemented as an array and things like 379 00:26:59,550 --> 00:26:59,880 that. 380 00:26:59,880 --> 00:27:06,870 And then we also don't always necessarily need to do a recursive algorithm for some of these to reversals. 381 00:27:07,770 --> 00:27:12,420 It is possible to do an iterative solution sometimes. 382 00:27:13,670 --> 00:27:19,490 And do some different reversals, so we might look at that as well, that's a little more challenging 383 00:27:19,490 --> 00:27:21,260 actually to most students. 384 00:27:21,260 --> 00:27:27,170 So we'll get into that and kind of push ourselves to figure out some iterative solutions as well. 385 00:27:27,710 --> 00:27:31,220 All right, I hope you enjoyed this lecture and I will see you in the next lecture.