1 00:00:00,630 --> 00:00:01,530 Hi everyone. 2 00:00:01,530 --> 00:00:03,660 Let's do this question right. 3 00:00:03,660 --> 00:00:10,470 For instance, methods for a binary search tree class to traverse the binary search tree method one. 4 00:00:10,470 --> 00:00:15,990 Traverse the tree breadth first and return an array that contains all the values of the binary search 5 00:00:15,990 --> 00:00:22,650 tree method to traverse the tree depth first in order, and return an array that contains all the values 6 00:00:22,650 --> 00:00:26,550 of the BST method three traverse the tree depth. 7 00:00:26,550 --> 00:00:32,040 First preorder and return an array that contains all the values of the BST, and finally traverse the 8 00:00:32,040 --> 00:00:34,680 tree depth, first post order and return an array. 9 00:00:34,680 --> 00:00:35,760 So this is the question. 10 00:00:35,760 --> 00:00:37,230 Now this is a standard question. 11 00:00:37,230 --> 00:00:42,840 So let's dive in and let's first discuss what's breadth first search and what is depth. 12 00:00:42,840 --> 00:00:47,130 First search and notice over here we have three types of depth first search. 13 00:00:47,130 --> 00:00:48,420 So let's get started. 14 00:00:48,420 --> 00:00:51,030 First we understand what's the expectation. 15 00:00:51,030 --> 00:00:53,910 And then let's discuss how we can solve this question. 16 00:00:53,910 --> 00:00:57,120 So over here I have a sample binary search tree. 17 00:00:57,120 --> 00:01:00,630 You can see everything to the right of 20 is greater than 20. 18 00:01:00,630 --> 00:01:03,420 Everything to the left of 20 is less than 20. 19 00:01:03,420 --> 00:01:05,670 So that's the binary search tree property. 20 00:01:05,670 --> 00:01:08,850 Now when we traverse this breadth first. 21 00:01:08,850 --> 00:01:11,370 So BFS is breadth first search right. 22 00:01:11,370 --> 00:01:13,860 So what we do is we go level by level. 23 00:01:13,860 --> 00:01:15,300 So this is level zero right. 24 00:01:15,300 --> 00:01:19,080 So we go first this level then we go in this level right. 25 00:01:19,080 --> 00:01:19,800 So 20. 26 00:01:19,830 --> 00:01:21,780 Then we take 1340. 27 00:01:21,780 --> 00:01:25,590 So we go to the next level 1013 and 43. 28 00:01:25,590 --> 00:01:28,350 And the next level is 811 and 41. 29 00:01:28,350 --> 00:01:30,450 So the output array should be this. 30 00:01:30,450 --> 00:01:32,220 When we do breadth first search. 31 00:01:32,220 --> 00:01:32,700 Right. 32 00:01:33,030 --> 00:01:38,700 So when we traverse the binary search tree with the breadth first approach we should be getting this 33 00:01:38,700 --> 00:01:42,810 output 2013 4010 1343 right. 34 00:01:42,810 --> 00:01:45,840 So this is the next level then 811 and 41. 35 00:01:45,840 --> 00:01:46,440 All right. 36 00:01:46,440 --> 00:01:48,390 So we have understood BFS. 37 00:01:48,390 --> 00:01:50,910 Now let's go ahead and understand DFS depth. 38 00:01:50,910 --> 00:01:54,810 First search or let's traverse the binary search tree depth first. 39 00:01:54,810 --> 00:01:58,620 Now as we have seen in the question there are three possibilities right. 40 00:01:58,620 --> 00:02:00,060 We can do this in three ways. 41 00:02:00,060 --> 00:02:04,230 We can do in order DFS, preorder DFS and post order DFS. 42 00:02:04,230 --> 00:02:06,810 Now let's try to understand what these mean. 43 00:02:06,810 --> 00:02:09,210 Let's get started with inorder DFS. 44 00:02:09,210 --> 00:02:16,080 Now when you do inorder DFS right, what you have to think of is first we process the left side of the 45 00:02:16,080 --> 00:02:17,040 particular node. 46 00:02:17,040 --> 00:02:19,470 Then we process the current node right. 47 00:02:19,470 --> 00:02:22,290 And then we process the right side of the current node. 48 00:02:22,290 --> 00:02:23,400 So this is the order. 49 00:02:23,400 --> 00:02:27,000 Now let's take a small example to understand what we mean with this. 50 00:02:27,000 --> 00:02:32,550 So over here I have a binary search tree and it just has three nodes ten nine and 11. 51 00:02:32,550 --> 00:02:33,000 All right. 52 00:02:33,000 --> 00:02:34,440 Now left node. 53 00:02:34,680 --> 00:02:36,150 We start with this one okay. 54 00:02:36,150 --> 00:02:36,780 This is the root. 55 00:02:36,810 --> 00:02:39,360 Now the left of this node is nine right. 56 00:02:39,360 --> 00:02:44,640 So when if we traverse this tree in order dfs the output array will look like this. 57 00:02:44,640 --> 00:02:46,320 First we go left which is nine. 58 00:02:46,320 --> 00:02:48,570 Then we process the current node which is ten. 59 00:02:48,570 --> 00:02:50,910 And then we get the right node which is 11. 60 00:02:50,910 --> 00:02:53,640 So the array would look like this 910 and 11. 61 00:02:53,640 --> 00:02:56,520 So this is inorder traversal of DFS type. 62 00:02:56,520 --> 00:02:57,210 All right. 63 00:02:57,630 --> 00:03:04,200 Now let's see how we can do DFS traversal on this binary search tree over here which is the sample one 64 00:03:04,200 --> 00:03:05,190 which we have taken. 65 00:03:05,190 --> 00:03:07,410 We start at the root which is 20. 66 00:03:07,410 --> 00:03:07,950 All right. 67 00:03:07,980 --> 00:03:09,960 Now first we go left right. 68 00:03:09,960 --> 00:03:11,280 So we come to 13. 69 00:03:11,280 --> 00:03:14,640 Right now when we come to 13 1313 is the current node. 70 00:03:14,640 --> 00:03:16,440 So again we go left right. 71 00:03:16,440 --> 00:03:18,990 And when we come to ten that's the current node. 72 00:03:18,990 --> 00:03:20,700 Again we go left which is eight. 73 00:03:20,700 --> 00:03:23,520 Now when we try to go left there is nothing more right. 74 00:03:23,520 --> 00:03:24,840 So there is nothing more over here. 75 00:03:24,840 --> 00:03:25,740 So we come back. 76 00:03:25,740 --> 00:03:28,020 So eight is the current node at this time. 77 00:03:28,020 --> 00:03:30,240 So we push eight to the array. 78 00:03:30,330 --> 00:03:32,880 And then we check if there is anything on the right. 79 00:03:32,880 --> 00:03:34,500 So again there is nothing on the right. 80 00:03:34,500 --> 00:03:35,340 So we come back. 81 00:03:35,340 --> 00:03:37,440 So from there we come back to ten. 82 00:03:37,440 --> 00:03:40,050 Now we have completed the left side of ten. 83 00:03:40,050 --> 00:03:41,340 Then we do the current. 84 00:03:41,340 --> 00:03:42,810 So at this point ten is current. 85 00:03:42,810 --> 00:03:43,980 So we push it to the array. 86 00:03:44,070 --> 00:03:45,810 Then we check the right of ten. 87 00:03:45,810 --> 00:03:46,140 All right. 88 00:03:46,140 --> 00:03:47,220 So we go this way. 89 00:03:47,220 --> 00:03:49,470 So over here we have 11 and we push it in. 90 00:03:49,470 --> 00:03:51,600 So what's actually happening is we come to 11. 91 00:03:51,600 --> 00:03:54,390 We check if it has anything in the left it does not have. 92 00:03:54,390 --> 00:03:55,470 So it comes back. 93 00:03:55,470 --> 00:03:56,670 So this is the current node. 94 00:03:56,670 --> 00:03:57,720 We push it to the array. 95 00:03:58,140 --> 00:03:58,530 Right. 96 00:03:58,530 --> 00:04:00,870 And then we check whether it has anything in the right. 97 00:04:00,870 --> 00:04:01,860 And it has nothing. 98 00:04:01,860 --> 00:04:04,200 So it comes back and we come back to ten. 99 00:04:04,650 --> 00:04:09,000 So at this point we have completed the left side of 13. 100 00:04:09,000 --> 00:04:09,210 Right. 101 00:04:09,210 --> 00:04:11,190 So this is the left side of this node over here. 102 00:04:11,190 --> 00:04:11,820 This 13. 103 00:04:11,820 --> 00:04:12,690 So that is done. 104 00:04:12,690 --> 00:04:13,680 So left is done. 105 00:04:13,680 --> 00:04:15,600 After that we process current right. 106 00:04:15,600 --> 00:04:19,170 So when we come back to ten then we go from 10 to 13. 107 00:04:19,170 --> 00:04:20,910 So 13 is current at this point. 108 00:04:20,910 --> 00:04:22,350 And we push it into the array. 109 00:04:22,890 --> 00:04:27,150 So the left of this node is done and the current node has been processed. 110 00:04:27,150 --> 00:04:29,670 Then we go to the right which is this 13 over here. 111 00:04:29,670 --> 00:04:31,650 And there is nothing in the left. 112 00:04:31,650 --> 00:04:32,520 So it comes back. 113 00:04:32,520 --> 00:04:33,270 This is current. 114 00:04:33,270 --> 00:04:34,830 At that point we push it to the array. 115 00:04:34,830 --> 00:04:35,940 We check its right. 116 00:04:35,940 --> 00:04:36,810 There is nothing over here. 117 00:04:36,810 --> 00:04:37,560 It comes back. 118 00:04:37,560 --> 00:04:38,550 So this is done. 119 00:04:38,550 --> 00:04:40,230 Now we go back to 13. 120 00:04:40,230 --> 00:04:43,590 And at this point the left of 20 is processed right. 121 00:04:43,590 --> 00:04:46,530 So this is the left of this node over here which is processed. 122 00:04:46,560 --> 00:04:49,650 Now we come back to 2020 is current right. 123 00:04:49,650 --> 00:04:51,330 So that's pushed to the array. 124 00:04:51,330 --> 00:04:52,740 And then we check its right. 125 00:04:52,740 --> 00:04:53,850 So we go to the right. 126 00:04:53,850 --> 00:04:55,110 So which is 40. 127 00:04:55,710 --> 00:05:00,090 When we go to the right 40 we check whether it has anything in its left. 128 00:05:00,310 --> 00:05:03,070 It does not have anything in its left, so it comes back. 129 00:05:03,070 --> 00:05:04,630 So 40 is current at this point. 130 00:05:04,630 --> 00:05:05,800 We process current right. 131 00:05:05,800 --> 00:05:09,430 And we push 40 to the array and then we check its right. 132 00:05:09,430 --> 00:05:10,750 So we go to the right direction. 133 00:05:10,750 --> 00:05:12,160 So we come to 43. 134 00:05:12,190 --> 00:05:16,180 Now when we come to 43 this is current at at that moment right. 135 00:05:16,180 --> 00:05:18,340 So then again we check its left. 136 00:05:18,340 --> 00:05:20,770 So we go to the left which is 41. 137 00:05:20,770 --> 00:05:23,320 And then this does not have anything in its left. 138 00:05:23,320 --> 00:05:24,760 So we push 41 to the array. 139 00:05:24,760 --> 00:05:26,950 It does not have anything in its right. 140 00:05:26,950 --> 00:05:28,960 So we come back to 43 at this point. 141 00:05:28,960 --> 00:05:29,230 Right. 142 00:05:29,230 --> 00:05:31,000 So we come back to 43. 143 00:05:31,000 --> 00:05:33,130 And at this point its left is done. 144 00:05:33,130 --> 00:05:34,270 So 43 is current. 145 00:05:34,270 --> 00:05:35,740 So that's pushed to the array. 146 00:05:35,830 --> 00:05:39,610 And then we come back to 40 and it's already it's done right. 147 00:05:39,610 --> 00:05:40,660 We are we are completed. 148 00:05:40,660 --> 00:05:41,860 We have already. 149 00:05:42,310 --> 00:05:43,780 That was the right side of 40. 150 00:05:43,780 --> 00:05:43,990 Right. 151 00:05:43,990 --> 00:05:45,880 So the left side of 40 was done. 152 00:05:45,880 --> 00:05:47,350 Current 40 was already pushed. 153 00:05:47,350 --> 00:05:49,960 And this is the right of 40 that is also completed. 154 00:05:49,960 --> 00:05:53,410 And that brings us to the end of in order DFS. 155 00:05:53,410 --> 00:05:59,140 So this is the output that we will get when we do inorder traversal of a binary search tree. 156 00:05:59,140 --> 00:05:59,470 Right. 157 00:05:59,470 --> 00:06:05,560 And notice over here when we do DFS in order, the array which you are getting over here is actually 158 00:06:05,560 --> 00:06:06,970 in the ascending order. 159 00:06:06,970 --> 00:06:12,310 So you have eight, ten, 11, 13, 13, 20, 40, 41, 43, which is the ascending order. 160 00:06:12,310 --> 00:06:18,250 Remember when we discussed removal in, uh, the binary search tree, when we wanted to remove a node, 161 00:06:18,250 --> 00:06:23,860 we discussed that we can replace that node with with its inorder predecessor or successor. 162 00:06:24,490 --> 00:06:25,630 Let me just clear this. 163 00:06:25,630 --> 00:06:26,020 All right. 164 00:06:26,050 --> 00:06:27,550 Now let's quickly revise that. 165 00:06:27,550 --> 00:06:30,820 Let's say you want to delete this node over here which is 20. 166 00:06:30,820 --> 00:06:36,340 Now you can replace this over here with the value of its in-order predecessor or successor. 167 00:06:36,340 --> 00:06:38,110 So over here we have 20. 168 00:06:38,110 --> 00:06:42,280 Now you can see that its successor is 40 and its predecessor is 13. 169 00:06:42,280 --> 00:06:42,610 Right. 170 00:06:42,610 --> 00:06:44,350 So this is this 14 over here. 171 00:06:44,350 --> 00:06:45,940 So remember how we got this. 172 00:06:45,970 --> 00:06:47,230 We moved to the right. 173 00:06:47,230 --> 00:06:50,410 And then we go as much to the left from here as we can. 174 00:06:50,410 --> 00:06:53,650 But because we don't have anything over here we stay over here itself. 175 00:06:53,650 --> 00:06:56,050 So this is its predecessor, its successor. 176 00:06:56,050 --> 00:06:56,290 Right. 177 00:06:56,290 --> 00:06:57,370 Inorder successor. 178 00:06:57,370 --> 00:06:59,080 Now what about the predecessor? 179 00:06:59,080 --> 00:07:02,740 So we go to the left and then we go right as much as we can. 180 00:07:02,740 --> 00:07:05,230 So this will be the inorder predecessor. 181 00:07:05,230 --> 00:07:06,550 So which is this one over here. 182 00:07:06,550 --> 00:07:08,620 So that's what we discussed over there. 183 00:07:08,620 --> 00:07:09,130 All right. 184 00:07:09,130 --> 00:07:12,070 So I just brought this up as a side point. 185 00:07:12,070 --> 00:07:19,030 So notice that when you do inorder DFS for a BST or a binary search tree you get the elements in ascending 186 00:07:19,030 --> 00:07:19,480 order. 187 00:07:19,480 --> 00:07:21,160 All right so we have discussed this. 188 00:07:21,610 --> 00:07:22,720 Let's now proceed. 189 00:07:22,720 --> 00:07:24,730 Now I've just placed this over here. 190 00:07:24,730 --> 00:07:27,580 This is the BFS order the breadth first search. 191 00:07:27,580 --> 00:07:29,020 And this is the in order. 192 00:07:29,020 --> 00:07:32,020 So let me just write that this is in order DFS. 193 00:07:32,020 --> 00:07:32,560 All right. 194 00:07:32,590 --> 00:07:37,600 Now let's proceed and look at these two preorder DFS and post order DFS. 195 00:07:37,600 --> 00:07:39,970 Now it's pretty similar to inorder DFS. 196 00:07:39,970 --> 00:07:44,410 We just have to change the order in which we do these three operations over here. 197 00:07:44,410 --> 00:07:48,250 So for the case of preorder we do the current operation first. 198 00:07:48,250 --> 00:07:51,010 Then we move to the left and then we move to the right. 199 00:07:51,010 --> 00:07:56,590 Now in the case of post order we do the left first then the right, and then we process the current 200 00:07:56,590 --> 00:07:56,890 node. 201 00:07:56,890 --> 00:08:02,590 So notice over here that you have left and right together in both these cases right you have left and 202 00:08:02,590 --> 00:08:03,310 right together. 203 00:08:03,310 --> 00:08:06,610 Now in the case of preorder you put current first. 204 00:08:06,640 --> 00:08:09,640 Now pre denotes before right. 205 00:08:09,640 --> 00:08:11,470 So you can just remember it in that way. 206 00:08:11,470 --> 00:08:13,570 So when you have pre order you put current first. 207 00:08:13,570 --> 00:08:16,990 And when you have post order post means last right or after. 208 00:08:16,990 --> 00:08:20,110 So you put current last and then left and right are together. 209 00:08:20,110 --> 00:08:22,360 So that's just a trick to remember this. 210 00:08:22,870 --> 00:08:23,290 All right. 211 00:08:23,320 --> 00:08:26,110 Now let's have our small binary search tree over here. 212 00:08:26,110 --> 00:08:28,090 So it just has three nodes. 213 00:08:28,090 --> 00:08:33,340 Now we have seen that when we do in-order traversal on this binary search tree we will get left which 214 00:08:33,340 --> 00:08:36,550 is nine, then current which is ten and then right which is 11. 215 00:08:36,550 --> 00:08:38,680 And we have seen that this is in ascending order. 216 00:08:38,680 --> 00:08:42,520 Now in the case of pre order traversal, first we go to the current. 217 00:08:42,520 --> 00:08:44,170 So we start at the root. 218 00:08:44,170 --> 00:08:45,190 So this is the current. 219 00:08:45,190 --> 00:08:46,720 So we push ten over here right. 220 00:08:46,720 --> 00:08:48,820 And then we go to the left which is nine. 221 00:08:48,820 --> 00:08:50,920 And then we go to the right which is 11. 222 00:08:50,920 --> 00:08:53,260 So we will get ten nine and 11. 223 00:08:53,260 --> 00:08:55,060 In the case of pre order DFS. 224 00:08:55,060 --> 00:09:00,910 And in the case of post order DFS first we go to the left which is 11 right or sorry nine. 225 00:09:00,910 --> 00:09:02,830 First we go to the left which is nine. 226 00:09:02,830 --> 00:09:05,260 And then we go to the right which is 11. 227 00:09:05,260 --> 00:09:07,480 And then we process the current node which is ten. 228 00:09:07,480 --> 00:09:09,610 So we get 911 and ten. 229 00:09:09,610 --> 00:09:12,910 So this is the post order DFS um traversal. 230 00:09:12,910 --> 00:09:18,580 So let's now go ahead and see pre order and post order DFS traversal for this binary search tree over 231 00:09:18,580 --> 00:09:19,060 here. 232 00:09:19,120 --> 00:09:19,420 All right. 233 00:09:19,420 --> 00:09:20,950 So let's just make some space. 234 00:09:21,460 --> 00:09:22,990 Now let's start with pre order. 235 00:09:22,990 --> 00:09:24,940 So we start at the root node. 236 00:09:24,940 --> 00:09:29,740 And you can see that in the case of pre order first itself we do the operation on the current node. 237 00:09:29,740 --> 00:09:31,720 Or we push this value to the array. 238 00:09:31,720 --> 00:09:33,580 So we push 20 to the array. 239 00:09:33,610 --> 00:09:34,090 All right. 240 00:09:34,090 --> 00:09:35,260 So this is the output array. 241 00:09:35,260 --> 00:09:36,550 Let's build it parallelly. 242 00:09:36,550 --> 00:09:38,530 Then what we do we move left right. 243 00:09:38,530 --> 00:09:39,910 So we move to 13. 244 00:09:39,910 --> 00:09:41,830 Now 13 is the current node right. 245 00:09:41,830 --> 00:09:44,350 So again we process the current node first. 246 00:09:44,350 --> 00:09:46,450 So we push 13 to the array. 247 00:09:46,450 --> 00:09:48,190 And then again we move left. 248 00:09:48,190 --> 00:09:49,870 So now ten is the current node. 249 00:09:49,870 --> 00:09:52,150 So again we push the current node to the array. 250 00:09:52,150 --> 00:09:53,380 So let's do that. 251 00:09:53,380 --> 00:09:57,430 So we put ten over here and we move again left because after current we do left right. 252 00:09:57,430 --> 00:09:59,260 So again we are now at eight. 253 00:09:59,260 --> 00:09:59,710 Eight is the. 254 00:09:59,840 --> 00:10:00,260 Current node. 255 00:10:00,260 --> 00:10:05,480 At this point, we push it to the array and we try to move left, but there is nothing in its left right. 256 00:10:05,480 --> 00:10:07,010 And again we try to move right. 257 00:10:07,010 --> 00:10:08,060 There is nothing in its right. 258 00:10:08,060 --> 00:10:09,050 So we come back. 259 00:10:09,050 --> 00:10:12,920 So at this point 410 we have processed the current node. 260 00:10:12,920 --> 00:10:14,720 This is the current node and we have done the left. 261 00:10:14,720 --> 00:10:16,280 So we go to the right right. 262 00:10:16,280 --> 00:10:17,660 So the right over here is 11. 263 00:10:17,660 --> 00:10:18,860 So we go to left. 264 00:10:18,860 --> 00:10:21,200 And 11 is the current node at this point. 265 00:10:21,200 --> 00:10:22,550 And we push it to the array. 266 00:10:22,550 --> 00:10:25,310 And we try left and right which is not there for it. 267 00:10:25,310 --> 00:10:26,270 And we come back. 268 00:10:26,270 --> 00:10:28,610 So at this point this is the left of 13. 269 00:10:28,610 --> 00:10:28,910 Right. 270 00:10:28,910 --> 00:10:30,200 So the left of 13. 271 00:10:30,200 --> 00:10:31,490 And this is current right. 272 00:10:31,490 --> 00:10:33,410 So current is done and left is done. 273 00:10:33,410 --> 00:10:34,820 So we go to the right. 274 00:10:35,300 --> 00:10:36,260 So this is the right. 275 00:10:36,260 --> 00:10:38,960 So we push that to the array and then we come back. 276 00:10:38,960 --> 00:10:42,140 So at this point this is the left of 20 right. 277 00:10:42,140 --> 00:10:43,010 The node 20. 278 00:10:43,010 --> 00:10:44,000 So the left is done. 279 00:10:44,000 --> 00:10:45,980 And over here we already did the current. 280 00:10:45,980 --> 00:10:47,120 So current is also done. 281 00:10:47,120 --> 00:10:48,350 Now we move to the right. 282 00:10:48,350 --> 00:10:50,060 So we move to the right which is 40. 283 00:10:50,090 --> 00:10:51,890 Now 40 is the current node right. 284 00:10:51,890 --> 00:10:53,540 So we push the current node to the array. 285 00:10:53,570 --> 00:10:54,800 So we have 40 over here. 286 00:10:54,800 --> 00:10:56,480 Now we try to move left. 287 00:10:56,480 --> 00:10:58,010 It does not have anything in the left. 288 00:10:58,010 --> 00:10:59,780 So we try to move to the right. 289 00:10:59,780 --> 00:11:01,130 So we go to 43. 290 00:11:01,130 --> 00:11:02,870 Now 43 is the current node. 291 00:11:02,870 --> 00:11:04,250 So we process the current node. 292 00:11:04,250 --> 00:11:06,350 We push 43 to the array right. 293 00:11:06,350 --> 00:11:09,410 Then we go left which is this part over here. 294 00:11:09,410 --> 00:11:11,270 So we go left which is 41. 295 00:11:11,270 --> 00:11:13,040 And that is the current node. 296 00:11:13,040 --> 00:11:13,820 We push to the array. 297 00:11:13,820 --> 00:11:14,780 We try to go left. 298 00:11:14,780 --> 00:11:17,120 We try to go right and it does not have anything. 299 00:11:17,120 --> 00:11:20,060 So at this point this is the left of 43. 300 00:11:20,060 --> 00:11:20,240 Right. 301 00:11:20,240 --> 00:11:21,230 So current is done. 302 00:11:21,230 --> 00:11:22,010 Left is done. 303 00:11:22,010 --> 00:11:23,150 And we try right. 304 00:11:23,150 --> 00:11:24,500 And it does not have any right. 305 00:11:24,500 --> 00:11:27,140 So this is the right of 40. 306 00:11:27,170 --> 00:11:27,350 Right. 307 00:11:27,350 --> 00:11:29,150 So left of 40 is empty. 308 00:11:29,180 --> 00:11:30,800 We have already processed 40. 309 00:11:30,800 --> 00:11:32,510 And we are done with the right of 40. 310 00:11:32,510 --> 00:11:33,560 So this is also done. 311 00:11:33,560 --> 00:11:35,030 This is the right of 20. 312 00:11:35,030 --> 00:11:37,730 So we have done 20 which is the current node. 313 00:11:37,730 --> 00:11:40,220 We have done its left and its right is also done. 314 00:11:40,220 --> 00:11:41,240 So we stop right. 315 00:11:41,240 --> 00:11:43,490 So all the call stack functions are done. 316 00:11:43,490 --> 00:11:49,730 They have returned and we get our array over here which is 2013, ten, eight, 11, 13, 40, 43 and 317 00:11:49,730 --> 00:11:50,210 41. 318 00:11:50,210 --> 00:11:54,650 So this is the DFS preorder traversal of this binary search tree. 319 00:11:54,650 --> 00:11:55,160 All right. 320 00:11:55,160 --> 00:11:56,750 So let's just keep this aside. 321 00:11:57,200 --> 00:12:01,820 And finally let's look at the post order DFS traversal of this binary search tree. 322 00:12:01,820 --> 00:12:05,180 So again we start at the root node which is 20. 323 00:12:05,210 --> 00:12:07,790 Now what we do is we first move left right. 324 00:12:07,790 --> 00:12:12,500 So you will see that 20 will be inserted at the very end in this array. 325 00:12:12,500 --> 00:12:14,990 So we move to the left which is 13. 326 00:12:14,990 --> 00:12:18,680 Again we move to the left again we move to the left and we reach eight right. 327 00:12:18,680 --> 00:12:20,360 And we try to move to move left. 328 00:12:20,360 --> 00:12:21,830 And there is nothing in its left. 329 00:12:21,830 --> 00:12:23,600 So we come back to eight. 330 00:12:23,600 --> 00:12:25,610 We try to go to its right again. 331 00:12:25,610 --> 00:12:26,780 Its right is also null. 332 00:12:26,780 --> 00:12:27,650 So we come back. 333 00:12:27,650 --> 00:12:30,020 So at this point eight is the current node. 334 00:12:30,020 --> 00:12:33,530 So we tried the left of this node and the right of this node which is empty. 335 00:12:33,530 --> 00:12:35,090 And then eight is now current. 336 00:12:35,090 --> 00:12:36,350 So we process this node. 337 00:12:36,350 --> 00:12:38,150 So we push eight to the array. 338 00:12:38,600 --> 00:12:41,870 Now we are done with the left of this node right. 339 00:12:41,870 --> 00:12:44,120 This is the left of node ten. 340 00:12:44,120 --> 00:12:45,350 Now the left is done. 341 00:12:45,350 --> 00:12:47,960 So we come back to ten and we move to its right. 342 00:12:48,440 --> 00:12:48,770 Right. 343 00:12:48,770 --> 00:12:50,360 So we have the right node over here. 344 00:12:50,360 --> 00:12:51,710 Again 11 is the node. 345 00:12:51,710 --> 00:12:54,170 We try its left and right which is null right. 346 00:12:54,170 --> 00:12:55,100 So we come back. 347 00:12:55,100 --> 00:12:56,930 So this is the current node and we push 11. 348 00:12:56,930 --> 00:13:00,710 So at this point the left and right of node ten is done. 349 00:13:00,710 --> 00:13:01,700 So we come back. 350 00:13:01,700 --> 00:13:03,830 And now we process the current node which is ten. 351 00:13:03,830 --> 00:13:05,090 So we push ten over here. 352 00:13:05,090 --> 00:13:07,550 So at this point this much is done right. 353 00:13:07,550 --> 00:13:09,470 This is the left of 13. 354 00:13:09,470 --> 00:13:10,400 So left is done. 355 00:13:10,400 --> 00:13:14,360 So now we move to the right of this node which is this 13 over here. 356 00:13:14,360 --> 00:13:16,640 And again it does not have any left or right. 357 00:13:16,640 --> 00:13:18,830 So we push this over here and we come back. 358 00:13:18,830 --> 00:13:23,600 So at this point the left of this 13 and the right of this 13 is done. 359 00:13:23,600 --> 00:13:26,330 So we process the current node which is this one over here. 360 00:13:26,330 --> 00:13:29,630 So we process this and we insert 13 to the array. 361 00:13:29,630 --> 00:13:33,590 So at this point this is the left of 20 right. 362 00:13:33,590 --> 00:13:35,030 So the left of 20 is done. 363 00:13:35,030 --> 00:13:38,030 So now we come back to 20 and process its right. 364 00:13:38,030 --> 00:13:38,270 Right. 365 00:13:38,270 --> 00:13:39,740 So after left we go to the right. 366 00:13:39,740 --> 00:13:41,030 So we come to 40. 367 00:13:41,060 --> 00:13:43,730 Now again from 40 we try left. 368 00:13:43,730 --> 00:13:45,290 It does not have anything in its left. 369 00:13:45,290 --> 00:13:46,190 So what do we do. 370 00:13:46,190 --> 00:13:47,270 We go to its right. 371 00:13:47,270 --> 00:13:48,650 So we come to 43. 372 00:13:48,680 --> 00:13:52,430 Now from 43 again we try left which is 41. 373 00:13:52,430 --> 00:13:55,220 So we come to 41 and then it does not have any left. 374 00:13:55,220 --> 00:13:56,030 It does not have any. 375 00:13:56,030 --> 00:13:56,330 Right. 376 00:13:56,330 --> 00:13:57,440 So it comes back. 377 00:13:57,440 --> 00:13:58,910 This is the current node at that point. 378 00:13:58,910 --> 00:14:00,020 And we push it to the array. 379 00:14:00,050 --> 00:14:03,080 So at this point we are done with the left of 43. 380 00:14:03,080 --> 00:14:06,380 Right now we come back to 43 and try for its right. 381 00:14:06,380 --> 00:14:08,090 Now we see it does not have a right. 382 00:14:08,090 --> 00:14:11,540 So again we come back and we process the current node which is 43. 383 00:14:11,540 --> 00:14:14,120 So 43 will be inserted to the array. 384 00:14:14,120 --> 00:14:20,750 So at this point the left of 40 is done which was empty and the right of 40 is completed. 385 00:14:20,750 --> 00:14:22,400 So 40 becomes the current node. 386 00:14:22,400 --> 00:14:24,650 And we process the current node which is 40. 387 00:14:24,650 --> 00:14:27,440 So that also gets entered inserted into our array. 388 00:14:27,440 --> 00:14:29,540 So at this point this is the. 389 00:14:30,270 --> 00:14:32,280 Left of the right of 20. 390 00:14:32,310 --> 00:14:32,520 Right. 391 00:14:32,520 --> 00:14:34,230 So we finished the left of 20. 392 00:14:34,230 --> 00:14:36,510 And just now we finished the right of 20. 393 00:14:36,510 --> 00:14:41,700 So we come back and we process the node 20 and we insert 20 to our array. 394 00:14:41,700 --> 00:14:43,800 And this is the postorder traversal. 395 00:14:43,800 --> 00:14:50,100 So this is the array that we get as output when we traverse this binary search tree with DFS Postorder. 396 00:14:50,100 --> 00:14:50,610 All right. 397 00:14:50,610 --> 00:14:57,210 So we have understood BFS and DFS and the three types of DFS which is in-order pre-order and Post-order. 398 00:14:57,210 --> 00:15:01,110 Now let's go ahead and try to see how we will code this solution. 399 00:15:01,110 --> 00:15:01,620 All right. 400 00:15:01,620 --> 00:15:04,620 So let's discuss the method and the complexity analysis. 401 00:15:04,620 --> 00:15:08,430 Now first let's start with breadth first search or BFS. 402 00:15:08,430 --> 00:15:11,130 So again we have our binary search tree over here. 403 00:15:11,130 --> 00:15:13,620 And we have already seen that the output expected. 404 00:15:13,620 --> 00:15:14,940 Is this right 20. 405 00:15:14,940 --> 00:15:16,890 Then we need 13 and 40. 406 00:15:16,890 --> 00:15:21,930 Then 1013 and 43 and then 811 and 41. 407 00:15:21,930 --> 00:15:23,250 So we go level by level. 408 00:15:23,250 --> 00:15:23,700 All right. 409 00:15:23,700 --> 00:15:25,260 So this is the expected output. 410 00:15:25,260 --> 00:15:27,600 Now let's see how we can code this. 411 00:15:27,600 --> 00:15:29,580 So for this we will use a queue. 412 00:15:29,580 --> 00:15:29,910 All right. 413 00:15:29,910 --> 00:15:31,470 So let's have this queue. 414 00:15:31,470 --> 00:15:33,300 And this is an empty queue over here. 415 00:15:33,300 --> 00:15:35,550 And we will also have an array. 416 00:15:35,550 --> 00:15:38,430 So the array will be the output array which is this one over here. 417 00:15:38,430 --> 00:15:39,480 And we will build it. 418 00:15:39,480 --> 00:15:44,910 Now we will start at the root node and we will push what is there in the root node into our queue. 419 00:15:44,910 --> 00:15:45,750 So let's do that. 420 00:15:45,750 --> 00:15:49,920 So we push 20 to our queue the value of the root node 20 to our queue. 421 00:15:49,920 --> 00:15:50,490 All right. 422 00:15:50,490 --> 00:15:52,500 Now we will have a while loop. 423 00:15:52,500 --> 00:15:57,810 And we will keep iterating or we'll keep repeating going through the loop as long as there is something 424 00:15:57,810 --> 00:15:58,740 in the queue. 425 00:15:58,770 --> 00:15:59,130 All right. 426 00:15:59,130 --> 00:16:03,390 So just let's walk through this code and you will understand how this is working. 427 00:16:03,840 --> 00:16:05,520 So we will have a while loop over here. 428 00:16:05,550 --> 00:16:08,610 Now inside this once we're inside this. 429 00:16:08,610 --> 00:16:11,070 So we are sure that there is something in the queue right. 430 00:16:11,070 --> 00:16:13,650 Because that's the condition while something is there in the queue. 431 00:16:13,650 --> 00:16:16,980 So once we are inside it we will take what is there in the queue. 432 00:16:16,980 --> 00:16:20,010 And that means we will take the first element right. 433 00:16:20,010 --> 00:16:23,130 So we will dequeue from the queue the first element. 434 00:16:23,250 --> 00:16:26,970 Because remember a queue is a Fifo data structure right. 435 00:16:26,970 --> 00:16:27,870 First in first out. 436 00:16:27,870 --> 00:16:31,200 So this is the leftmost element in this array. 437 00:16:31,200 --> 00:16:33,840 Over here will be what was entered first right. 438 00:16:33,840 --> 00:16:36,930 So we will take that out and we will push it to the array. 439 00:16:36,930 --> 00:16:39,180 So we will have 20 pushed into the array. 440 00:16:39,180 --> 00:16:44,130 So let me just write it over here we have dequeue and push inside this while loop. 441 00:16:44,580 --> 00:16:47,430 And after this we are now at node 20 right. 442 00:16:47,430 --> 00:16:50,220 We will look whether it has a left child or a right child. 443 00:16:50,220 --> 00:16:53,490 And if it has a left child, we will enqueue that value to the queue. 444 00:16:53,490 --> 00:16:56,250 And if it has a right child, we will put that value to the queue. 445 00:16:56,250 --> 00:16:59,340 So let's do that over here n queue left right. 446 00:16:59,340 --> 00:17:01,230 So over here the left child is 13. 447 00:17:01,230 --> 00:17:04,980 So we put that value into the queue and then we enqueue the right child. 448 00:17:04,980 --> 00:17:06,690 So over here we have 40. 449 00:17:06,690 --> 00:17:09,780 Again the value of the right child 40 is put into the queue. 450 00:17:09,780 --> 00:17:11,070 So we have 13 and 40. 451 00:17:11,070 --> 00:17:12,630 And that's the end of the while loop. 452 00:17:12,630 --> 00:17:15,750 Now again we check whether there is something in the queue. 453 00:17:15,780 --> 00:17:17,040 Yes there are two elements. 454 00:17:17,040 --> 00:17:19,020 Right now you can see 13 and 40. 455 00:17:19,020 --> 00:17:22,350 Are this layer like this level which is level one. 456 00:17:22,350 --> 00:17:26,280 So we can see there are two elements over here 13 and 40. 457 00:17:26,280 --> 00:17:27,840 So yes there is something over here. 458 00:17:27,840 --> 00:17:29,010 So again what do we do. 459 00:17:29,040 --> 00:17:31,410 We dequeue from the queue which is 13. 460 00:17:31,410 --> 00:17:32,040 Right. 461 00:17:32,040 --> 00:17:36,570 So we dequeue from the queue which is 13 and we push it to the array. 462 00:17:36,570 --> 00:17:38,490 So we have 13 put into the array. 463 00:17:38,490 --> 00:17:41,700 Now the node where we are at is 13. 464 00:17:41,700 --> 00:17:45,090 Right now we check whether it has a left or a right child. 465 00:17:45,090 --> 00:17:47,460 And if it has we push those values to the queue. 466 00:17:47,460 --> 00:17:50,820 So in this case enqueue left will put ten inside right. 467 00:17:50,820 --> 00:17:54,150 And enqueue right will put the value 13 inside our queue. 468 00:17:54,150 --> 00:17:54,930 And that's it. 469 00:17:54,930 --> 00:17:57,420 So again our queue is not empty right. 470 00:17:57,420 --> 00:17:58,380 So what do we do. 471 00:17:58,380 --> 00:18:02,730 We take the first value from the queue and we put it to the array. 472 00:18:02,730 --> 00:18:04,890 So we dequeue and we push to the array. 473 00:18:04,890 --> 00:18:07,170 And then now we are at this node 40. 474 00:18:07,170 --> 00:18:10,470 And we put the values of its children to the queue. 475 00:18:10,470 --> 00:18:13,650 So in this case there is no left child but there is a right child. 476 00:18:13,650 --> 00:18:15,570 So 43 gets put into the queue. 477 00:18:16,080 --> 00:18:16,500 All right. 478 00:18:16,500 --> 00:18:18,360 So again the queue is not empty. 479 00:18:18,360 --> 00:18:22,170 So at this point what the next value that we take out is ten. 480 00:18:22,170 --> 00:18:24,600 So we take out ten and we push it to the array. 481 00:18:24,600 --> 00:18:26,970 And now we are at node ten right. 482 00:18:26,970 --> 00:18:30,000 And its children eight and 11 are added to the queue. 483 00:18:30,540 --> 00:18:30,990 All right. 484 00:18:30,990 --> 00:18:33,930 So again after that the queue is still not empty. 485 00:18:33,960 --> 00:18:36,030 Now we go to 13 right 13. 486 00:18:36,030 --> 00:18:40,050 So we again dequeue 13 and we push it to the array. 487 00:18:40,050 --> 00:18:43,980 Now 13 over here does not have any children so nothing gets added to the queue. 488 00:18:43,980 --> 00:18:48,780 Next we dequeue 43 and we push it to the array. 489 00:18:48,780 --> 00:18:50,760 And then 43 has the child 41. 490 00:18:50,760 --> 00:18:52,560 So that value gets added to the queue. 491 00:18:52,560 --> 00:18:55,860 Next again we take out eight eight does not have any children. 492 00:18:55,860 --> 00:18:59,490 Similarly 11 does not have any children and 41 does not have any children. 493 00:18:59,490 --> 00:19:03,390 So eight, 11 and 41 respectively get added to the array. 494 00:19:03,390 --> 00:19:09,780 And that gives us this output over here 2013 4010, 13, 43, eight, 11 and 41. 495 00:19:09,780 --> 00:19:12,300 So this is how we do the breadth first search. 496 00:19:12,300 --> 00:19:15,510 So notice the method over here we use the queue. 497 00:19:15,510 --> 00:19:17,640 And then we start from the root. 498 00:19:17,640 --> 00:19:22,620 Now we take that value out from the queue put it to the array right. 499 00:19:22,620 --> 00:19:24,810 So that will be the first element in our output array. 500 00:19:24,810 --> 00:19:27,030 And then its children get added to the queue. 501 00:19:27,030 --> 00:19:27,210 Right. 502 00:19:27,210 --> 00:19:29,760 So 13 and 40 were added over here after that. 503 00:19:30,010 --> 00:19:33,160 We take out 13, and then ten and 13 were added. 504 00:19:33,160 --> 00:19:38,800 So you can see that we are slowly, uh, going from level by level and we are going left to right, 505 00:19:38,800 --> 00:19:42,820 and we are adding those values over here and it's children get added later. 506 00:19:42,820 --> 00:19:43,060 Right. 507 00:19:43,060 --> 00:19:48,760 So this is how we tackle the breadth first search so that we get the output and the arrays. 508 00:19:48,760 --> 00:19:51,310 The array contains values level by level. 509 00:19:51,310 --> 00:19:51,820 All right. 510 00:19:51,850 --> 00:19:56,020 Now let's go ahead and discuss the complexity analysis of this solution. 511 00:19:57,010 --> 00:20:00,940 Now the time complexity for this solution will be o of N, right? 512 00:20:00,940 --> 00:20:07,900 Because we are just visiting every node once and doing some constant time operation on it by dequeuing 513 00:20:07,900 --> 00:20:09,130 and then pushing it to the array. 514 00:20:09,130 --> 00:20:09,400 Right. 515 00:20:09,400 --> 00:20:12,910 So we are just visiting every node once and doing some constant operations. 516 00:20:12,910 --> 00:20:15,670 So the time complexity is clearly O of n. 517 00:20:15,670 --> 00:20:17,800 Now what about the space complexity? 518 00:20:17,830 --> 00:20:21,940 The space complexity over here is O of n because we are making an array. 519 00:20:21,940 --> 00:20:22,210 Right. 520 00:20:22,210 --> 00:20:25,840 And the size of the array will be of length n because there are n elements. 521 00:20:25,840 --> 00:20:31,750 Now if this was not the case, if we just had to visit and print it, for example, and we were not 522 00:20:31,750 --> 00:20:37,870 storing those values in an array, for example, in that case the space complexity will be O of W, 523 00:20:37,870 --> 00:20:42,130 where w is the maximum width of the binary search tree, right. 524 00:20:42,130 --> 00:20:47,020 So this will be the approximate maximum size of the queue at any time. 525 00:20:47,020 --> 00:20:48,970 So we are just making this queue over here. 526 00:20:48,970 --> 00:20:49,240 Right. 527 00:20:49,240 --> 00:20:55,660 So this queues maximum size approximately will be of the order of the width of the binary search tree. 528 00:20:56,080 --> 00:21:01,630 Now over here when we build the queue you can see that at some point we had maximum of four elements. 529 00:21:01,630 --> 00:21:01,930 Right. 530 00:21:01,930 --> 00:21:03,430 So that is the width. 531 00:21:03,430 --> 00:21:04,690 Width at this case is three. 532 00:21:04,690 --> 00:21:06,730 This is the maximum width three plus one. 533 00:21:06,730 --> 00:21:09,130 So it's w plus one in this case. 534 00:21:09,130 --> 00:21:10,420 But this is just a constant. 535 00:21:10,420 --> 00:21:11,380 So we can avoid that. 536 00:21:11,380 --> 00:21:17,950 So the space complexity will be o of w where w is the width of the queue the maximum width of the queue. 537 00:21:17,950 --> 00:21:19,000 In this case it's three. 538 00:21:19,030 --> 00:21:24,040 Now let's look at the worst case and the best case in terms of space complexity. 539 00:21:24,040 --> 00:21:27,010 And we are taking the case where we are not building an array. 540 00:21:27,010 --> 00:21:27,400 Right. 541 00:21:27,400 --> 00:21:32,560 So we are taking this case where we probably just have to traverse the binary search tree and print 542 00:21:32,560 --> 00:21:33,130 those values. 543 00:21:33,130 --> 00:21:34,330 So we are not creating an array. 544 00:21:34,330 --> 00:21:37,210 So in this case the space complexity is O of w. 545 00:21:37,210 --> 00:21:40,180 Now let's look at the worst and best case of O of w. 546 00:21:40,180 --> 00:21:40,720 All right. 547 00:21:41,550 --> 00:21:44,460 Now for the worst case. 548 00:21:44,460 --> 00:21:46,980 If the tree is a balanced tree, right? 549 00:21:46,980 --> 00:21:49,950 If the tree is balanced, then it will have the maximum width right? 550 00:21:49,950 --> 00:21:56,850 So in that case there will be log n levels which is the height, and the last level will have two to 551 00:21:56,850 --> 00:21:58,110 the power height nodes. 552 00:21:58,110 --> 00:21:58,470 Right. 553 00:21:58,470 --> 00:22:03,840 So that will be two to the power log n and two to the power log n is nothing but n right. 554 00:22:03,840 --> 00:22:09,060 So in this case the space complexity will be o of n. 555 00:22:09,060 --> 00:22:11,370 Now again how is it. 556 00:22:11,370 --> 00:22:12,600 How did we get that. 557 00:22:12,600 --> 00:22:16,590 We found that w in this case will be two to the power of height. 558 00:22:16,590 --> 00:22:17,010 Right. 559 00:22:17,010 --> 00:22:19,620 And in the case of a balanced tree and height is log n. 560 00:22:19,620 --> 00:22:21,270 So two to the power log n is n. 561 00:22:21,270 --> 00:22:24,300 So in this case in the worst case w can be n. 562 00:22:24,300 --> 00:22:28,170 So the worst case complexity over here will be o of n. 563 00:22:28,170 --> 00:22:30,330 Now again two of log n is equal to n. 564 00:22:30,330 --> 00:22:31,920 Let me just quickly show that to you. 565 00:22:31,920 --> 00:22:34,560 If you have not remembered that, no problem. 566 00:22:34,560 --> 00:22:38,610 Let's quickly discuss that log eight for example is equal to three. 567 00:22:38,610 --> 00:22:43,950 And we know that that's so because two to the power three two to the power three is equal to eight. 568 00:22:44,520 --> 00:22:44,940 All right. 569 00:22:44,940 --> 00:22:51,390 Now instead of this three which I have over here, let me just replace it with log eight so I can say 570 00:22:51,390 --> 00:22:53,190 two to the power log eight. 571 00:22:53,190 --> 00:22:53,490 Right. 572 00:22:53,490 --> 00:22:55,770 So this three I am replacing it with log eight. 573 00:22:55,770 --> 00:22:59,760 So two to the power log eight is equal to eight right. 574 00:22:59,760 --> 00:23:02,970 So you can see two to the power log n is equal to n. 575 00:23:02,970 --> 00:23:04,560 So that is what we have applied over here. 576 00:23:04,560 --> 00:23:05,820 That's how we got that. 577 00:23:05,820 --> 00:23:06,450 The worst case. 578 00:23:06,450 --> 00:23:09,240 In the worst case the width of the tree will be n. 579 00:23:09,240 --> 00:23:13,470 And in that case the space complexity will be o of n. 580 00:23:13,470 --> 00:23:13,950 All right. 581 00:23:13,950 --> 00:23:15,450 And what about the best case. 582 00:23:15,450 --> 00:23:19,260 The best case will be O of one if the tree is skewed right. 583 00:23:19,260 --> 00:23:25,440 If if there is just one node per level and you have a binary search tree that looks like a linked list, 584 00:23:25,440 --> 00:23:30,630 for example, something like this one, two, three, etc. and then for something like this, right. 585 00:23:30,630 --> 00:23:33,060 So over here that's a skewed binary search tree. 586 00:23:33,060 --> 00:23:36,870 Now if that is the case then the maximum width is just one right. 587 00:23:36,870 --> 00:23:39,840 So the best case space complexity will be O of one. 588 00:23:39,840 --> 00:23:42,090 In the case of a skewed tree, all right. 589 00:23:42,090 --> 00:23:44,130 So we have discussed the breadth first search. 590 00:23:44,460 --> 00:23:46,500 We have discussed how we will implement it. 591 00:23:46,500 --> 00:23:52,590 And we have seen that the time complexity of BFS is O of n and the space complexity is O of n. 592 00:23:52,590 --> 00:23:56,610 Because over here we were creating an array of size n, right. 593 00:23:56,610 --> 00:24:00,870 But if that was not the case, the space complexity would be O of W. 594 00:24:00,870 --> 00:24:01,380 All right. 595 00:24:01,410 --> 00:24:08,190 Now let's go ahead and discuss the the complexity analysis of the three DFS approaches which we discussed, 596 00:24:08,190 --> 00:24:10,530 which is in-order pre-order and post order. 597 00:24:10,530 --> 00:24:15,780 And again, before we go to the complexity analysis, let's discuss how we will implement this in code. 598 00:24:15,780 --> 00:24:19,320 So we will have a function let's call it Traf. 599 00:24:19,320 --> 00:24:21,960 And then this function will take in a node. 600 00:24:21,960 --> 00:24:22,350 All right. 601 00:24:22,350 --> 00:24:25,620 So once we reach a node then what is it that we do. 602 00:24:25,620 --> 00:24:28,230 Let's just first discuss in-order traversal. 603 00:24:28,230 --> 00:24:31,080 And then the other two are just pretty much similar. 604 00:24:31,080 --> 00:24:31,470 All right. 605 00:24:31,470 --> 00:24:36,660 So once we reach a node over here you can see we have to go to the left node first. 606 00:24:36,660 --> 00:24:38,340 Then we process the current node. 607 00:24:38,340 --> 00:24:40,110 And then we go to the right node. 608 00:24:40,110 --> 00:24:42,210 So this is what we will do over here. 609 00:24:42,210 --> 00:24:44,520 So we have this function Trav. 610 00:24:44,520 --> 00:24:46,020 And again we are passing in a node. 611 00:24:46,020 --> 00:24:47,820 So we are at a particular node. 612 00:24:47,820 --> 00:24:50,040 Then we will check if there is a left node. 613 00:24:50,040 --> 00:24:55,020 So if there is a left node then we will recursively call the same function trav. 614 00:24:55,020 --> 00:24:57,180 And we will pass that particular left node. 615 00:24:57,180 --> 00:24:57,630 All right. 616 00:24:57,660 --> 00:25:01,320 Now once it comes back we will process the current node. 617 00:25:01,320 --> 00:25:05,760 And processing the current node means pushing the value of the current node to the array. 618 00:25:05,760 --> 00:25:07,230 So that's processing the current node. 619 00:25:07,230 --> 00:25:07,560 Right. 620 00:25:07,560 --> 00:25:09,810 So over here we will say array dot push. 621 00:25:09,810 --> 00:25:11,730 And we will push the value of the current node. 622 00:25:11,730 --> 00:25:13,920 And again this is just pseudo code right. 623 00:25:13,920 --> 00:25:16,110 So I'm just writing over here. 624 00:25:16,110 --> 00:25:17,910 But it should be the value of the current node. 625 00:25:17,910 --> 00:25:21,690 And then finally after we have we are done with processing the current node. 626 00:25:21,690 --> 00:25:24,630 We will just go and look at the right node. 627 00:25:24,630 --> 00:25:26,520 Or we will traverse the right side right. 628 00:25:26,520 --> 00:25:30,900 So that we will be done by again recursively calling the draw function. 629 00:25:30,900 --> 00:25:33,120 And over here we will pass the right node. 630 00:25:33,120 --> 00:25:33,900 So that's it. 631 00:25:33,900 --> 00:25:39,150 So this will give us the in-order traversal the in-order traversal of this binary search tree. 632 00:25:39,150 --> 00:25:40,920 Let's quickly see what's happening over here. 633 00:25:40,920 --> 00:25:42,240 We start at 20. 634 00:25:42,900 --> 00:25:43,290 All right. 635 00:25:43,290 --> 00:25:45,660 So we are let's say we are inside this function. 636 00:25:45,660 --> 00:25:46,830 Does it have a left node. 637 00:25:46,830 --> 00:25:47,100 Yes. 638 00:25:47,100 --> 00:25:48,900 So we go over here again. 639 00:25:48,900 --> 00:25:52,020 Now this is we are again in the next call of traverse. 640 00:25:52,020 --> 00:25:52,290 Right. 641 00:25:52,290 --> 00:25:54,180 So this is 13 at this point. 642 00:25:54,180 --> 00:25:55,950 Does it have a left uh node. 643 00:25:55,950 --> 00:25:56,700 Yes it has. 644 00:25:56,700 --> 00:25:59,250 So at this point again we move left. 645 00:25:59,250 --> 00:26:02,160 Again we go for a new call of the function. 646 00:26:02,160 --> 00:26:02,430 Right. 647 00:26:02,430 --> 00:26:04,410 So again we go left at this point. 648 00:26:04,470 --> 00:26:06,930 And at this point there is nothing in the left right. 649 00:26:06,930 --> 00:26:10,560 So we come we it returns back and then we are at this. 650 00:26:10,560 --> 00:26:11,580 This is the current node. 651 00:26:11,580 --> 00:26:13,470 And then we push eight to the array. 652 00:26:13,470 --> 00:26:15,600 So that's how we discuss that. 653 00:26:15,600 --> 00:26:18,960 In the case of in-order traversal we will first get eight over here right. 654 00:26:18,960 --> 00:26:20,100 So eight is done. 655 00:26:20,700 --> 00:26:22,800 And that's the current node at this point. 656 00:26:22,800 --> 00:26:24,990 And this now we will try its right. 657 00:26:24,990 --> 00:26:26,130 And again there's nothing. 658 00:26:26,130 --> 00:26:27,180 So we will return. 659 00:26:27,180 --> 00:26:29,250 So at this point the left of ten is done. 660 00:26:29,250 --> 00:26:31,470 Now we will push ten which is the current node. 661 00:26:31,470 --> 00:26:33,150 And then we will go to its right. 662 00:26:33,150 --> 00:26:33,510 Right. 663 00:26:33,510 --> 00:26:35,850 So that's pushing happens over here. 664 00:26:35,850 --> 00:26:37,680 And going to its right happens over here. 665 00:26:37,680 --> 00:26:41,160 So we go to 11 and then we again call the function. 666 00:26:41,280 --> 00:26:42,240 You try to go left. 667 00:26:42,240 --> 00:26:43,980 But we can't because there's nothing. 668 00:26:43,980 --> 00:26:45,960 Then we push the value, which is 11. 669 00:26:45,960 --> 00:26:48,180 We try to go right, we can't, so we return. 670 00:26:48,180 --> 00:26:51,330 So at this point the left of 13 is done right. 671 00:26:51,330 --> 00:26:54,000 So then we push 13 which is the current node. 672 00:26:54,000 --> 00:26:54,780 So this is the current. 673 00:26:54,780 --> 00:26:58,650 So we push 13 and then we move to its right which is this 13 over here. 674 00:26:58,650 --> 00:27:02,670 So again and that's how we build the array over here which we have already discussed. 675 00:27:02,670 --> 00:27:07,470 So this is the way that we will code the DFS inorder traversal. 676 00:27:07,470 --> 00:27:07,830 All right. 677 00:27:07,830 --> 00:27:09,240 So let's just make some space. 678 00:27:09,240 --> 00:27:11,610 And I keep this aside now. 679 00:27:12,490 --> 00:27:14,800 Let's discuss pre order and post order. 680 00:27:15,310 --> 00:27:20,710 When you notice this over here you can see that this difference between these is just miniute right. 681 00:27:20,710 --> 00:27:22,540 It's just the difference between the order. 682 00:27:22,540 --> 00:27:25,780 So that's the only difference that you will see when you code this. 683 00:27:25,780 --> 00:27:27,490 So let's discuss pre order. 684 00:27:27,490 --> 00:27:32,050 In the case of pre order we will push or do the operation on the current node first which is this. 685 00:27:32,050 --> 00:27:34,750 Over here we will push the value of the current node to the array. 686 00:27:34,780 --> 00:27:36,880 Then we go left and then we go right. 687 00:27:36,880 --> 00:27:39,130 So you can see we have just changed the order right. 688 00:27:39,130 --> 00:27:40,960 We have just made this first. 689 00:27:40,960 --> 00:27:42,730 And then we have this and then we have this. 690 00:27:42,730 --> 00:27:44,890 So this gives us pre order. 691 00:27:44,890 --> 00:27:47,440 Now in the case of post order this will be last. 692 00:27:47,440 --> 00:27:48,580 That's the only difference. 693 00:27:48,580 --> 00:27:50,470 So we have array dot push last. 694 00:27:50,470 --> 00:27:51,370 First we go left. 695 00:27:51,370 --> 00:27:52,240 Then we go right. 696 00:27:52,240 --> 00:27:54,550 And then we do the operation on the current node. 697 00:27:54,550 --> 00:27:57,280 That is we push the value of the current node to the array. 698 00:27:57,280 --> 00:28:02,080 So that is how we will implement DFS in order pre order and post order. 699 00:28:02,080 --> 00:28:02,500 All right. 700 00:28:02,530 --> 00:28:05,890 Now let's quickly look at the complexity analysis of this solution. 701 00:28:05,890 --> 00:28:08,290 Now it will be the same for all these three right. 702 00:28:08,290 --> 00:28:09,940 We are just changing the order over here. 703 00:28:09,940 --> 00:28:16,060 Now the time complexity will be equal to O of N because we have to visit every node once and do some 704 00:28:16,060 --> 00:28:17,770 constant time operation on that node. 705 00:28:17,770 --> 00:28:18,070 Right. 706 00:28:18,070 --> 00:28:20,320 Like for example, you have to push that value to the array. 707 00:28:20,320 --> 00:28:22,930 So the time complexity will be O of n. 708 00:28:22,930 --> 00:28:26,890 You can say O of constant into n, and this is just a constant. 709 00:28:26,890 --> 00:28:30,460 So we can remove it and we get o of n as the time complexity. 710 00:28:30,460 --> 00:28:32,500 Now what about the space complexity? 711 00:28:33,010 --> 00:28:37,390 The space complexity over here will be O of N because we are building an array, right? 712 00:28:37,390 --> 00:28:40,000 We are building an array of size n two return. 713 00:28:40,000 --> 00:28:44,620 Now if this was not the case, if we did not want to do that, and let's say we are just traversing 714 00:28:44,620 --> 00:28:47,170 and printing the values, we are not creating a new array. 715 00:28:47,170 --> 00:28:52,330 In that case, the space complexity will be O of D, where d is the maximum depth. 716 00:28:52,330 --> 00:28:52,660 Right? 717 00:28:52,660 --> 00:28:55,930 Because we will be using multiple calls on the call stack. 718 00:28:55,930 --> 00:28:58,720 So we'll use some memory from the call stack. 719 00:28:58,720 --> 00:29:01,060 So that will depend on the depth of the tree right. 720 00:29:01,060 --> 00:29:02,110 Or the height of the tree. 721 00:29:02,650 --> 00:29:06,460 So the space complexity over here will be O of d.