WEBVTT 1 00:00:00.140 --> 00:00:01.380 Hi, and welcome back. 2 00:00:01.380 --> 00:00:03.270 In this video we're going to look at 3 00:00:03.270 --> 00:00:07.323 traversal of binary trees: how you can go through elements. 4 00:00:08.850 --> 00:00:11.960 So there are three types of traversal in binary trees. 5 00:00:11.960 --> 00:00:15.930 We've got something called inorder traversal, 6 00:00:15.930 --> 00:00:18.690 where the first thing you do is you go left, 7 00:00:18.690 --> 00:00:20.820 then you check the node, and then you go right. 8 00:00:20.820 --> 00:00:24.150 We're gonna look at exactly what this means in a moment. 9 00:00:24.150 --> 00:00:26.260 You've got preorder traversal, 10 00:00:26.260 --> 00:00:27.520 where you check the node first, 11 00:00:27.520 --> 00:00:29.300 and then you go left, and then you go right. 12 00:00:29.300 --> 00:00:31.950 And finally, you've got postorder traversal, 13 00:00:31.950 --> 00:00:33.710 where you go left first, then right, 14 00:00:33.710 --> 00:00:35.520 and then you check the node. 15 00:00:35.520 --> 00:00:38.040 So, what does this all mean? 16 00:00:38.040 --> 00:00:40.320 Well, let's look at a few examples. 17 00:00:40.320 --> 00:00:42.680 We've got three identical trees here. 18 00:00:42.680 --> 00:00:45.140 We are going to navigate them 19 00:00:45.140 --> 00:00:48.350 inorder, preorder, and postorder 20 00:00:48.350 --> 00:00:50.313 and see what we come up with. 21 00:00:52.260 --> 00:00:55.800 In the inorder traversal, the first thing we do is 22 00:00:55.800 --> 00:00:57.810 we are at the top of the tree, 23 00:00:57.810 --> 00:00:59.080 so in these examples 24 00:00:59.080 --> 00:01:02.220 we always start at the very top of the tree, 25 00:01:02.220 --> 00:01:05.360 and what you do first is you go left, 26 00:01:05.360 --> 00:01:08.170 because that's what inorder traversal means. 27 00:01:08.170 --> 00:01:10.410 When you arrive at a node, 28 00:01:10.410 --> 00:01:11.840 the first thing you do is you go left 29 00:01:11.840 --> 00:01:14.400 and you go to its left node. 30 00:01:14.400 --> 00:01:17.963 So the first thing we do is we would go to the left node. 31 00:01:18.900 --> 00:01:21.980 Now we are at the node nine. 32 00:01:21.980 --> 00:01:23.160 We are at the new node, 33 00:01:23.160 --> 00:01:27.247 so once again we apply inorder and we go left. 34 00:01:27.247 --> 00:01:29.373 Notice that it doesn't have a left node, 35 00:01:30.330 --> 00:01:32.113 so that's not something we can do. 36 00:01:33.180 --> 00:01:35.150 Because we don't have a left node here, 37 00:01:35.150 --> 00:01:40.150 we're going to, staying at the node nine, check the node, 38 00:01:40.640 --> 00:01:43.220 and we're going to, let's say, print it out. 39 00:01:43.220 --> 00:01:45.673 So this prints out node number nine, 40 00:01:46.800 --> 00:01:50.120 and now we've checked the node, so we go right, 41 00:01:50.120 --> 00:01:51.973 and we move over to 13. 42 00:01:53.330 --> 00:01:57.380 Then we go left: doesn't have one. 43 00:01:57.380 --> 00:01:58.270 We check the node. 44 00:01:58.270 --> 00:02:00.797 We print 13 out, and then we go right, 45 00:02:00.797 --> 00:02:02.240 and it doesn't have one, 46 00:02:02.240 --> 00:02:05.930 and now that we've finished going left, printing, 47 00:02:05.930 --> 00:02:08.700 and then going right for the node 13, 48 00:02:08.700 --> 00:02:10.663 we go back to number nine, 49 00:02:12.150 --> 00:02:15.210 and then we go back to 14 50 00:02:15.210 --> 00:02:17.210 because we're also finished at number 9. 51 00:02:18.730 --> 00:02:21.520 So again, what happened here is we started at 14. 52 00:02:21.520 --> 00:02:23.210 We went left. 53 00:02:23.210 --> 00:02:24.490 We appeared at 9. 54 00:02:24.490 --> 00:02:25.730 We went left. 55 00:02:25.730 --> 00:02:26.640 Then we printed 9, 56 00:02:26.640 --> 00:02:27.930 and then we went right, 57 00:02:27.930 --> 00:02:29.700 and we ended up at 13. 58 00:02:29.700 --> 00:02:31.250 We went left: didn't have one. 59 00:02:31.250 --> 00:02:32.150 We printed. 60 00:02:32.150 --> 00:02:34.120 Then we went right: didn't have one. 61 00:02:34.120 --> 00:02:36.810 We went back to 9, back to fourteen. 62 00:02:36.810 --> 00:02:38.300 So now we're going to print 14, 63 00:02:38.300 --> 00:02:41.303 since we've already gone through all of its left nodes, 64 00:02:42.630 --> 00:02:45.130 and then we're going to go right at 14. 65 00:02:45.130 --> 00:02:46.690 We end up at 22. 66 00:02:46.690 --> 00:02:48.830 Gonna go left: doesn't have one. 67 00:02:48.830 --> 00:02:50.911 So we're going to print it out, 68 00:02:50.911 --> 00:02:52.703 and then we're gonna go right, 69 00:02:52.703 --> 00:02:53.797 and then we're gonna go left: doesn't have one. 70 00:02:55.311 --> 00:02:56.703 So we're gonna print it out, 71 00:02:56.703 --> 00:02:59.670 and then we're gonna go right, and that's it. 72 00:02:59.670 --> 00:03:03.573 We have finished the inorder traversal of this tree. 73 00:03:04.650 --> 00:03:06.210 For every node, 74 00:03:06.210 --> 00:03:09.483 the first thing you do is you go to its left node. 75 00:03:10.490 --> 00:03:15.093 So you'll end up at the node that is most left of your tree. 76 00:03:16.030 --> 00:03:17.703 Then you will print that node out, 77 00:03:17.703 --> 00:03:19.920 and you will go to the right node, 78 00:03:19.920 --> 00:03:21.823 and so forth for every parent. 79 00:03:23.530 --> 00:03:27.750 Notice what you end up here with is the ordered list, 80 00:03:27.750 --> 00:03:30.770 because you started at the most left node, 81 00:03:30.770 --> 00:03:32.770 and you made your way over to the right. 82 00:03:35.120 --> 00:03:38.120 So that's what inorder traversal is. 83 00:03:38.120 --> 00:03:40.220 Looking at preorder, 84 00:03:40.220 --> 00:03:42.180 the first thing you do is you check the node, 85 00:03:42.180 --> 00:03:43.290 and in this case we're gonna say that 86 00:03:43.290 --> 00:03:45.610 checking the node is equivalent to printing it out. 87 00:03:45.610 --> 00:03:46.460 So the first thing you do is, 88 00:03:46.460 --> 00:03:48.210 starting at 14, 89 00:03:48.210 --> 00:03:50.390 you would print it out. 90 00:03:50.390 --> 00:03:52.030 Then you'd go left, 91 00:03:52.030 --> 00:03:53.330 and now you're at a new node. 92 00:03:53.330 --> 00:03:56.090 So once again you print it out, 93 00:03:56.090 --> 00:03:57.120 and then you go left, 94 00:03:57.120 --> 00:03:57.953 but it doesn't have one. 95 00:03:57.953 --> 00:03:59.160 So then you go right. 96 00:03:59.160 --> 00:04:00.100 Then you're at the new node, 97 00:04:00.100 --> 00:04:01.370 and you print it out. 98 00:04:01.370 --> 00:04:02.203 Then you go left, 99 00:04:02.203 --> 00:04:03.036 and you go right, 100 00:04:03.036 --> 00:04:04.110 but it doesn't have either. 101 00:04:04.110 --> 00:04:06.790 So you end up, again, at 14. 102 00:04:06.790 --> 00:04:08.140 Then you're gonna go right, 103 00:04:09.270 --> 00:04:11.320 and print 22 out. 104 00:04:11.320 --> 00:04:13.050 Then you're gonna go left: doesn't have one. 105 00:04:13.050 --> 00:04:14.060 Then you're gonna go right. 106 00:04:14.060 --> 00:04:15.700 You're gonna end up at 34, 107 00:04:15.700 --> 00:04:17.223 and you're gonna print that out. 108 00:04:18.610 --> 00:04:21.360 This is the preorder traversal. 109 00:04:21.360 --> 00:04:23.670 Before going to another node, 110 00:04:23.670 --> 00:04:25.070 we print the node. 111 00:04:25.070 --> 00:04:26.381 Then we go left, 112 00:04:26.381 --> 00:04:28.740 then we go right. 113 00:04:28.740 --> 00:04:30.380 Notice that what you end up here 114 00:04:30.380 --> 00:04:32.580 is something that looks a little bit random. 115 00:04:33.630 --> 00:04:34.463 We're gonna look at 116 00:04:34.463 --> 00:04:37.373 exactly what this is useful for in a few moments, 117 00:04:38.630 --> 00:04:41.880 and finally, the postorder traversal. 118 00:04:41.880 --> 00:04:43.237 The first thing you do is you go left, 119 00:04:43.237 --> 00:04:44.750 and then you go right, 120 00:04:44.750 --> 00:04:46.590 and then you check the node. 121 00:04:46.590 --> 00:04:47.863 so we go left. 122 00:04:48.800 --> 00:04:50.200 We are at nine, 123 00:04:50.200 --> 00:04:51.240 so we go left, 124 00:04:51.240 --> 00:04:52.230 but it doesn't have one. 125 00:04:52.230 --> 00:04:53.640 We go right. 126 00:04:53.640 --> 00:04:54.800 We end up at 13. 127 00:04:54.800 --> 00:04:55.690 Now we're at 13, 128 00:04:55.690 --> 00:04:56.720 So we go left. 129 00:04:56.720 --> 00:04:57.553 Doesn't have one. 130 00:04:57.553 --> 00:04:58.386 We go right. 131 00:04:58.386 --> 00:04:59.219 Doesn't have one. 132 00:04:59.219 --> 00:05:00.840 We print it out. 133 00:05:00.840 --> 00:05:02.040 We're back at nine. 134 00:05:02.040 --> 00:05:03.460 We've already gone right, 135 00:05:03.460 --> 00:05:05.220 so now we print it out. 136 00:05:05.220 --> 00:05:06.340 We're back at 14, 137 00:05:06.340 --> 00:05:07.253 so we go right. 138 00:05:08.190 --> 00:05:09.270 Now we're at 22, 139 00:05:09.270 --> 00:05:10.420 so we go left. 140 00:05:10.420 --> 00:05:11.610 Then we go right, 141 00:05:11.610 --> 00:05:13.200 and we end up at 34. 142 00:05:13.200 --> 00:05:14.033 We go left, 143 00:05:14.033 --> 00:05:15.140 then we go right. 144 00:05:15.140 --> 00:05:16.020 Doesn't have any, 145 00:05:16.020 --> 00:05:17.840 so we print it out. 146 00:05:17.840 --> 00:05:19.230 We're back at 22. 147 00:05:19.230 --> 00:05:20.280 We print it out. 148 00:05:20.280 --> 00:05:21.490 We're back at 14. 149 00:05:21.490 --> 00:05:22.323 We print it out. 150 00:05:23.780 --> 00:05:27.630 Hopefully, this is not terribly confusing. 151 00:05:27.630 --> 00:05:29.600 All we're doing here is changing 152 00:05:29.600 --> 00:05:32.680 whether we go to a different node first, 153 00:05:32.680 --> 00:05:34.703 or whether we print things out first. 154 00:05:36.740 --> 00:05:38.840 We're going to look at some examples in code 155 00:05:38.840 --> 00:05:40.690 in a few moments. 156 00:05:40.690 --> 00:05:43.950 So inorder traversal is useful 157 00:05:43.950 --> 00:05:47.960 to get an ordered list out of a binary tree. 158 00:05:47.960 --> 00:05:50.610 Often it's also useful for printing the tree out, 159 00:05:50.610 --> 00:05:51.830 if you want to show it to your users, 160 00:05:51.830 --> 00:05:53.450 you want to maybe display it 161 00:05:53.450 --> 00:05:56.140 in a nice ordered fashion like an ordered list. 162 00:05:56.140 --> 00:05:58.263 You can do that with inorder traversal. 163 00:05:59.910 --> 00:06:01.870 Preorder traversal is actually useful 164 00:06:01.870 --> 00:06:05.163 for saving the tree so it can be reconstructed later. 165 00:06:06.610 --> 00:06:08.060 This may be a bit abstract 166 00:06:08.060 --> 00:06:11.400 because we've not looked at creating trees yet, 167 00:06:11.400 --> 00:06:13.760 but we're going to do that shortly. 168 00:06:13.760 --> 00:06:17.110 So what happens here is that you end up with a list 169 00:06:17.110 --> 00:06:20.170 that essentially represents your tree. 170 00:06:20.170 --> 00:06:21.950 The first element in the list 171 00:06:21.950 --> 00:06:25.633 is also the topmost element in your tree. 172 00:06:26.470 --> 00:06:30.650 Then you have the left side of the tree, nine and 13, 173 00:06:30.650 --> 00:06:34.500 and then you have the right side of the tree, 22 and 34. 174 00:06:34.500 --> 00:06:35.870 We're going to look at preorder 175 00:06:35.870 --> 00:06:39.313 and how we can use it to reconstruct a tree in code shortly, 176 00:06:40.920 --> 00:06:43.640 and finally, postorder traversal is useful 177 00:06:43.640 --> 00:06:46.170 for deleting the tree. 178 00:06:46.170 --> 00:06:49.410 We're going to briefly talk about deleting nodes, 179 00:06:49.410 --> 00:06:53.473 but it is a more complicated concept in binary trees. 180 00:06:54.610 --> 00:06:57.420 Don't worry too much if it's not fully clear 181 00:06:57.420 --> 00:06:58.720 what these are for, 182 00:06:58.720 --> 00:06:59.680 and how you implement them, 183 00:06:59.680 --> 00:07:00.700 and how you use them. 184 00:07:00.700 --> 00:07:02.290 We're going to look at some code samples, 185 00:07:02.290 --> 00:07:03.290 as I've been saying. 186 00:07:04.280 --> 00:07:07.053 With that said, I'll see you in the very next video.