1 00:00:00,710 --> 00:00:01,820 Welcome back. 2 00:00:01,820 --> 00:00:07,580 Let's now go ahead and write the function to invert the given binary tree recursively. 3 00:00:07,580 --> 00:00:09,980 So over here is the previous function that we have written. 4 00:00:09,980 --> 00:00:12,380 So let's write the new function here itself. 5 00:00:12,380 --> 00:00:15,530 So let's call this function invert recursive. 6 00:00:19,450 --> 00:00:22,630 And this function is also going to take in the root. 7 00:00:22,750 --> 00:00:24,790 So we have root over here. 8 00:00:24,940 --> 00:00:31,090 Now once we are inside this function we will think of the base case because this is going to be a recursive 9 00:00:31,090 --> 00:00:31,840 solution. 10 00:00:31,840 --> 00:00:36,310 So the base case is going to be when the root is equal to null we will just return. 11 00:00:36,310 --> 00:00:40,030 So if root is equal to null. 12 00:00:41,640 --> 00:00:43,860 In that case, we will just return. 13 00:00:43,890 --> 00:00:46,980 Now remember this is not necessarily to be called root. 14 00:00:46,980 --> 00:00:48,480 Let me just call this node. 15 00:00:48,480 --> 00:00:51,540 So this is actually the node with which we are calling the function. 16 00:00:51,540 --> 00:00:55,020 So when that is actually equal to null we will just return. 17 00:00:55,020 --> 00:00:55,530 All right. 18 00:00:55,530 --> 00:01:00,510 Now if this is not the case then for that particular node we will swap. 19 00:01:00,750 --> 00:01:06,270 So at this point we are going to swap the left and the right of that particular node using a temp variable. 20 00:01:06,270 --> 00:01:07,860 So let's say const temp. 21 00:01:09,800 --> 00:01:14,060 Is equal to root or at this point node right, node dot left. 22 00:01:14,060 --> 00:01:15,920 Let's call it left. 23 00:01:15,920 --> 00:01:18,950 Let me just take this down a bit so that we can see this. 24 00:01:18,950 --> 00:01:21,860 And then we will say node dot left. 25 00:01:23,090 --> 00:01:25,160 Is equal to no dot, right? 26 00:01:26,090 --> 00:01:29,840 And node dot right is equal to temp. 27 00:01:30,380 --> 00:01:32,990 So in this way we are swapping the left and right. 28 00:01:32,990 --> 00:01:39,590 Now we are going to recursively call the same function the invert recursive function on the left node 29 00:01:39,590 --> 00:01:40,790 and the right node. 30 00:01:40,790 --> 00:01:42,320 So this is how this function works. 31 00:01:42,320 --> 00:01:43,970 So let's call this recursively. 32 00:01:43,970 --> 00:01:46,220 So we have invert recursive. 33 00:01:46,220 --> 00:01:48,350 And we are going to pass the left node. 34 00:01:48,350 --> 00:01:49,670 So node dot left. 35 00:01:51,370 --> 00:01:53,410 And we are doing the same thing for the right node. 36 00:01:53,410 --> 00:01:57,520 So invert recursive and we will pass node dot right. 37 00:01:58,540 --> 00:01:59,410 And that's it. 38 00:01:59,410 --> 00:02:02,470 And once we are back, we just need to return the node. 39 00:02:02,470 --> 00:02:04,600 So that's mentioned in the question right. 40 00:02:04,600 --> 00:02:08,500 So we take in the root and we're going to return the root. 41 00:02:08,500 --> 00:02:10,480 So over here it's going to be the node. 42 00:02:10,480 --> 00:02:13,000 So initially we will call this function with the root. 43 00:02:13,000 --> 00:02:16,330 So when we return it we will be returning that particular root itself. 44 00:02:16,330 --> 00:02:17,320 So that's it. 45 00:02:17,320 --> 00:02:19,870 So let's go ahead and test our code. 46 00:02:20,880 --> 00:02:25,530 So let me just comment this and we're going to call the invert recursive function. 47 00:02:25,530 --> 00:02:28,020 And we will pass three dot root over here. 48 00:02:30,980 --> 00:02:31,280 All right. 49 00:02:31,280 --> 00:02:34,460 Now again, let me just draw this binary tree. 50 00:02:34,460 --> 00:02:39,290 So we are having this binary tree and then we will be inverting this one over here using our recursive 51 00:02:39,290 --> 00:02:39,950 function. 52 00:02:40,840 --> 00:02:44,320 So this is the binary tree which we have created over here. 53 00:02:44,320 --> 00:02:44,740 All right. 54 00:02:44,770 --> 00:02:48,910 Now let's go ahead and call the function and check whether our code is working. 55 00:02:48,910 --> 00:02:50,170 So let's run it. 56 00:02:50,800 --> 00:02:51,190 All right. 57 00:02:51,190 --> 00:02:52,090 So we have done it. 58 00:02:52,090 --> 00:02:53,740 Now let's check what we are getting. 59 00:02:53,740 --> 00:02:57,250 So we have again the root is the same which is one. 60 00:02:57,250 --> 00:02:58,600 Now let's open it up. 61 00:02:58,600 --> 00:03:01,750 So let's take a look at the left and right child of this. 62 00:03:01,750 --> 00:03:03,220 Once it is inverted right. 63 00:03:03,220 --> 00:03:06,160 So we have the left is three and the right is two. 64 00:03:06,190 --> 00:03:07,270 So yes it's working. 65 00:03:07,270 --> 00:03:09,400 So let's just draw this out parallely. 66 00:03:09,400 --> 00:03:12,700 So we have one and the left is three and the right is two. 67 00:03:12,730 --> 00:03:13,810 So yes this worked. 68 00:03:13,810 --> 00:03:14,800 Now let's continue. 69 00:03:14,800 --> 00:03:15,940 Let's open this up. 70 00:03:15,940 --> 00:03:17,200 And then we have the left. 71 00:03:17,200 --> 00:03:18,250 Over here is five. 72 00:03:19,760 --> 00:03:21,230 And the right is null. 73 00:03:21,230 --> 00:03:23,630 And you can see, yes, this part has been reversed. 74 00:03:23,630 --> 00:03:24,080 Right? 75 00:03:24,170 --> 00:03:25,820 This part also has been reversed. 76 00:03:25,850 --> 00:03:27,110 Now let's continue. 77 00:03:27,110 --> 00:03:28,040 Let's open this up. 78 00:03:28,040 --> 00:03:31,070 We see that over here the left is null. 79 00:03:31,070 --> 00:03:34,280 So the left is null and the right has value seven. 80 00:03:34,280 --> 00:03:36,290 So yes we can see this part. 81 00:03:36,290 --> 00:03:37,340 This is this was null right. 82 00:03:37,340 --> 00:03:39,230 So this is also now reversed. 83 00:03:39,230 --> 00:03:39,800 All right. 84 00:03:39,800 --> 00:03:41,990 Now let's go ahead and open this up. 85 00:03:41,990 --> 00:03:44,540 And we will get null and null. 86 00:03:44,540 --> 00:03:45,560 So we have null and null. 87 00:03:45,560 --> 00:03:47,000 So yes this is also correct. 88 00:03:47,000 --> 00:03:49,040 Now let's check the children of two. 89 00:03:50,560 --> 00:03:53,710 So we go this way we can see that the left is null. 90 00:03:55,300 --> 00:03:57,220 And the right is for. 91 00:03:57,250 --> 00:04:00,100 So yes, this part has been inverted. 92 00:04:00,100 --> 00:04:02,470 And let's open this part over here. 93 00:04:02,770 --> 00:04:05,590 We can see the left is null and the right has value six. 94 00:04:06,160 --> 00:04:11,620 So this is null and this has six which is this part has been inverted. 95 00:04:11,650 --> 00:04:13,630 Now if we just open this up we'll see. 96 00:04:13,630 --> 00:04:15,460 It has null and null as the children. 97 00:04:15,460 --> 00:04:17,260 So yes our function is working. 98 00:04:17,260 --> 00:04:20,590 Now let's just trace the code and see what's happening over here. 99 00:04:21,130 --> 00:04:25,090 So for this let me just um, take an example. 100 00:04:25,090 --> 00:04:28,690 Let's just, uh, make this a bit smaller so that we can see it. 101 00:04:32,710 --> 00:04:34,720 All right, so, yes, we are over here. 102 00:04:35,610 --> 00:04:37,380 Now let's try to trace the function. 103 00:04:37,380 --> 00:04:39,120 So this is the binary tree. 104 00:04:39,120 --> 00:04:41,070 So initially one is passed right. 105 00:04:41,070 --> 00:04:42,600 So initially one is passed. 106 00:04:42,600 --> 00:04:44,160 Now we are checking if this is null. 107 00:04:44,160 --> 00:04:45,120 No it's not null. 108 00:04:45,120 --> 00:04:48,450 So we come over here and then this part swaps these two. 109 00:04:48,450 --> 00:04:48,630 Right. 110 00:04:48,630 --> 00:04:50,190 So we we get these two. 111 00:04:50,220 --> 00:04:51,330 These two will be swapped. 112 00:04:51,330 --> 00:04:54,870 And then the children of it is not yet swapped at this point. 113 00:04:54,870 --> 00:04:58,740 Now we are going to recursively call it at the left which is for this one. 114 00:04:58,740 --> 00:04:59,160 Right. 115 00:04:59,160 --> 00:05:04,950 So when we call it over here its children that is these two will be swapped and we will get it five 116 00:05:04,950 --> 00:05:05,910 and N over here. 117 00:05:05,910 --> 00:05:07,530 But these are not yet swapped. 118 00:05:07,560 --> 00:05:11,010 Now again that's in in a recursive call. 119 00:05:11,010 --> 00:05:11,160 Right. 120 00:05:11,160 --> 00:05:16,470 So after this is swapped again when we come over here it will recursively call it for its children. 121 00:05:16,470 --> 00:05:18,750 And we will see that this over here is null. 122 00:05:18,750 --> 00:05:20,850 So it will come over here and it will return. 123 00:05:20,850 --> 00:05:22,050 So this is returning. 124 00:05:22,050 --> 00:05:26,250 Then it will come over here and it will swap its children, which is just null and null. 125 00:05:26,250 --> 00:05:28,290 So it does not have any impact. 126 00:05:28,290 --> 00:05:30,720 And once this is done we will return. 127 00:05:30,720 --> 00:05:32,670 So this function call will be over right. 128 00:05:32,670 --> 00:05:35,580 For swapping the call where we swap these two. 129 00:05:35,580 --> 00:05:37,500 So that was part of um. 130 00:06:05,910 --> 00:06:09,270 Now let's just trace what is happening in the code. 131 00:06:09,270 --> 00:06:13,110 So this is the binary tree and we are passing the root of it. 132 00:06:13,110 --> 00:06:13,410 Right. 133 00:06:13,410 --> 00:06:15,060 So initially we are calling it with the root. 134 00:06:15,060 --> 00:06:18,210 So the node is initially the root which is one. 135 00:06:18,270 --> 00:06:19,530 We are checking if this is null. 136 00:06:19,530 --> 00:06:20,370 No it's not. 137 00:06:20,370 --> 00:06:24,090 So we come over here and we will swap its left and right. 138 00:06:24,090 --> 00:06:25,470 So this is created right. 139 00:06:25,470 --> 00:06:28,470 So this part is done but its children are not yet swapped. 140 00:06:28,470 --> 00:06:31,110 And let me also write the call stack over here. 141 00:06:31,110 --> 00:06:35,370 We just called the recursive function with the root node which was one. 142 00:06:35,370 --> 00:06:36,960 So it's there in the call stack. 143 00:06:36,960 --> 00:06:37,980 It's not yet returned. 144 00:06:37,980 --> 00:06:39,930 So we come over here at this point. 145 00:06:39,930 --> 00:06:43,440 Now we are going to call the same function with the left which is with three. 146 00:06:43,440 --> 00:06:45,000 So let me write this over here. 147 00:06:45,000 --> 00:06:48,240 So we have R and we are calling it with node three. 148 00:06:48,240 --> 00:06:50,460 So again we come inside the function. 149 00:06:50,460 --> 00:06:52,890 We see that this node over here is not null. 150 00:06:52,890 --> 00:06:53,850 This is not null. 151 00:06:53,850 --> 00:06:55,800 So we swap its left and right. 152 00:06:55,800 --> 00:06:59,880 So this these two get swapped and we get five and n over here. 153 00:06:59,880 --> 00:07:00,540 Right. 154 00:07:00,540 --> 00:07:03,150 And then we again come over here. 155 00:07:03,150 --> 00:07:06,600 And we are going to call it with the left node which is five at this point. 156 00:07:06,600 --> 00:07:12,660 So let me write that over here we recursively call the same function with five with node five. 157 00:07:12,660 --> 00:07:16,200 So we come inside this we are checking if the node is null. 158 00:07:16,200 --> 00:07:17,220 No its not null. 159 00:07:17,220 --> 00:07:20,280 So we come over here and we swap its children. 160 00:07:20,280 --> 00:07:20,460 Right. 161 00:07:20,460 --> 00:07:25,530 So these two these seven and n get swapped and we get n and 7NN means null. 162 00:07:25,530 --> 00:07:27,570 We get null and seven over here right. 163 00:07:27,570 --> 00:07:33,210 So again we come over here and we are going to call the same invert recursive function with the left 164 00:07:33,210 --> 00:07:34,140 node which is null. 165 00:07:34,140 --> 00:07:36,720 So we are going to call it with null at this point. 166 00:07:38,170 --> 00:07:40,120 And we come inside the function again. 167 00:07:40,120 --> 00:07:42,850 And over here we see that that particular node is null. 168 00:07:42,850 --> 00:07:44,020 So this returns right. 169 00:07:44,020 --> 00:07:44,950 So this returns. 170 00:07:44,950 --> 00:07:46,390 So we come back over here. 171 00:07:46,390 --> 00:07:47,980 So this is done. 172 00:07:47,980 --> 00:07:52,480 And this is done for the call where we had the node as five. 173 00:07:52,480 --> 00:07:57,730 So we come to this part which is the recursive call on the right node which is seven over here. 174 00:07:57,730 --> 00:07:59,440 So a call is made. 175 00:07:59,710 --> 00:08:01,420 Let me write it as R with seven. 176 00:08:01,420 --> 00:08:04,360 So the recursive call is made with node seven. 177 00:08:04,360 --> 00:08:05,890 Again its children are swapped. 178 00:08:05,890 --> 00:08:06,610 We come inside. 179 00:08:06,610 --> 00:08:07,990 We see that this is not null. 180 00:08:07,990 --> 00:08:09,100 So we come over here. 181 00:08:09,100 --> 00:08:11,560 Its children are swapped which is null and null. 182 00:08:11,560 --> 00:08:12,820 So these are swapped. 183 00:08:12,820 --> 00:08:14,110 It does not have any impact. 184 00:08:14,110 --> 00:08:17,500 Then we call it on its left child which is again null. 185 00:08:17,740 --> 00:08:19,930 So we come over here and we write it. 186 00:08:19,930 --> 00:08:21,820 So we have a call with null. 187 00:08:22,490 --> 00:08:24,770 We come inside the function, it returns. 188 00:08:25,010 --> 00:08:26,480 Then we come over here. 189 00:08:26,480 --> 00:08:26,840 Right. 190 00:08:26,840 --> 00:08:32,270 So this is part of the call with node seven its children were swapped and we called it on its left child. 191 00:08:32,270 --> 00:08:35,480 Now we are going to call it on its right child which again is null. 192 00:08:35,480 --> 00:08:38,510 So that is going to be another null call which will return. 193 00:08:38,510 --> 00:08:38,930 All right. 194 00:08:38,930 --> 00:08:39,950 So this is done. 195 00:08:39,950 --> 00:08:44,660 So at this point for the call with node seven the left and right is done. 196 00:08:44,660 --> 00:08:46,550 And this this call will be over. 197 00:08:46,550 --> 00:08:46,700 Right. 198 00:08:46,700 --> 00:08:48,470 So this call is over and it will return. 199 00:08:48,470 --> 00:08:49,310 It will return. 200 00:08:49,310 --> 00:08:53,690 Now this was part of the call where we had node five. 201 00:08:53,690 --> 00:08:55,250 Its left was done and its right. 202 00:08:55,250 --> 00:08:56,480 So this is also done right. 203 00:08:56,480 --> 00:08:57,710 So this will return. 204 00:08:57,710 --> 00:08:58,760 So this will return. 205 00:08:58,760 --> 00:09:00,110 So this will return. 206 00:09:00,110 --> 00:09:02,180 And this call is done now. 207 00:09:02,180 --> 00:09:04,670 Now we are coming over here for three. 208 00:09:04,670 --> 00:09:06,890 So we did the call for the left. 209 00:09:06,890 --> 00:09:08,390 That's how we came to five. 210 00:09:08,390 --> 00:09:11,090 But now we are going to the right which is this part over here. 211 00:09:11,090 --> 00:09:11,360 Right. 212 00:09:11,360 --> 00:09:13,550 So we are going to the right and again its null. 213 00:09:13,550 --> 00:09:17,330 So it will come to the call stack but it will immediately return at this point. 214 00:09:17,330 --> 00:09:17,870 All right. 215 00:09:17,870 --> 00:09:19,430 So this will now return. 216 00:09:20,060 --> 00:09:21,440 This will now return right. 217 00:09:21,440 --> 00:09:22,460 So this is done. 218 00:09:22,460 --> 00:09:23,720 Now we come over here. 219 00:09:23,720 --> 00:09:26,480 This was part of the left call of node one. 220 00:09:26,480 --> 00:09:28,250 Now we go in this direction right. 221 00:09:28,250 --> 00:09:30,020 So we are going to call the right node. 222 00:09:30,020 --> 00:09:33,530 So this is the particular node at this point which is this line. 223 00:09:33,530 --> 00:09:33,950 Right. 224 00:09:33,950 --> 00:09:36,050 So we again come inside the function. 225 00:09:36,050 --> 00:09:37,070 This is not null. 226 00:09:37,070 --> 00:09:37,880 So what do we do. 227 00:09:37,880 --> 00:09:38,330 We swap. 228 00:09:38,330 --> 00:09:39,770 So these two get swapped right. 229 00:09:39,770 --> 00:09:43,460 So these two these two get swapped for and n and we get n and four over here. 230 00:09:43,460 --> 00:09:45,350 And then we call it on its left. 231 00:09:45,350 --> 00:09:47,150 It will return because this is null. 232 00:09:47,150 --> 00:09:50,090 Then we call it on its right which is this line over here. 233 00:09:50,090 --> 00:09:52,190 So this is the current node at this point. 234 00:09:52,190 --> 00:09:53,930 So its children will be swapped. 235 00:09:53,930 --> 00:09:55,580 So these two will be swapped. 236 00:09:55,580 --> 00:09:56,960 And we get N and six. 237 00:09:56,960 --> 00:10:00,770 Over here we make the call on its left which will return because this is null. 238 00:10:00,770 --> 00:10:03,830 Then we make the call on its right again its null and null. 239 00:10:03,830 --> 00:10:06,680 So it does not have any impact and then it will return. 240 00:10:06,680 --> 00:10:07,940 We come back over here. 241 00:10:07,940 --> 00:10:10,340 And then this also returns and this also returns. 242 00:10:10,340 --> 00:10:11,090 And we are done right. 243 00:10:11,090 --> 00:10:11,840 So we are done. 244 00:10:11,840 --> 00:10:14,630 So this is how the recursive function works. 245 00:10:14,630 --> 00:10:18,560 Now what about the space and time complexity of this solution. 246 00:10:18,560 --> 00:10:19,940 Let's take a quick look. 247 00:10:19,940 --> 00:10:23,120 Now the time complexity is again going to be o of n right. 248 00:10:23,120 --> 00:10:25,280 The time complexity is nothing but O of n. 249 00:10:25,280 --> 00:10:26,090 Why is that so? 250 00:10:26,090 --> 00:10:29,600 Because we are just traversing through the binary tree right. 251 00:10:29,600 --> 00:10:33,830 So for every node, for every node we will make one recursive call. 252 00:10:33,830 --> 00:10:36,440 So for every node we will make one recursive call. 253 00:10:36,440 --> 00:10:38,390 So there will be a total of n calls. 254 00:10:38,390 --> 00:10:42,830 So for each of these calls we are doing some constant time operations which is swapping. 255 00:10:42,830 --> 00:10:44,390 And then again calling. 256 00:10:44,390 --> 00:10:47,750 Calling the functions again is already accounted for in our N calls. 257 00:10:47,750 --> 00:10:52,640 So for each of these we are just doing some constant operations time operations inside the calls. 258 00:10:52,640 --> 00:10:54,950 So the time complexity is going to be O of N. 259 00:10:54,950 --> 00:10:56,870 What about the space complexity. 260 00:10:56,870 --> 00:11:00,560 It will depend on the on the maximum depth right. 261 00:11:00,560 --> 00:11:03,080 So in this case we will do one call over here. 262 00:11:03,080 --> 00:11:04,280 And then it comes over here. 263 00:11:04,280 --> 00:11:05,450 We do a call over here. 264 00:11:05,450 --> 00:11:06,410 We do a call over here. 265 00:11:06,410 --> 00:11:07,400 We do a call over here. 266 00:11:07,400 --> 00:11:09,440 And then we do a call over here for its child. 267 00:11:09,440 --> 00:11:09,620 Right. 268 00:11:09,620 --> 00:11:13,610 So there's a total of one two, three, four five calls at a time. 269 00:11:13,610 --> 00:11:20,630 So we can say that the space complexity is going to be the of the order of the maximum depth. 270 00:11:21,880 --> 00:11:27,220 Now, if the tree is balanced, this is going to be of the order of log of n. 271 00:11:28,150 --> 00:11:28,480 All right. 272 00:11:28,480 --> 00:11:34,240 So because for a balanced binary tree the maximum depth is going to be of the order of log of n. 273 00:11:34,240 --> 00:11:34,390 Right. 274 00:11:34,390 --> 00:11:38,260 So the space complexity over here is going to be maximum depth. 275 00:11:38,260 --> 00:11:42,430 And if it is a balanced binary tree it's going to be O of log of n.