1 00:00:00,660 --> 00:00:01,680 Welcome back. 2 00:00:01,680 --> 00:00:05,490 Let's now go ahead and code the solution which we have already discussed. 3 00:00:05,520 --> 00:00:09,180 Now over here we will be creating a class node. 4 00:00:09,540 --> 00:00:11,970 Because each of these values is going to be a node. 5 00:00:11,970 --> 00:00:12,360 Right. 6 00:00:12,360 --> 00:00:14,700 So we will have a class node for this. 7 00:00:14,700 --> 00:00:17,730 And then we will have our class binary search tree. 8 00:00:17,730 --> 00:00:18,210 Right. 9 00:00:18,210 --> 00:00:19,590 So let's write that over here. 10 00:00:19,590 --> 00:00:21,000 This is binary search tree. 11 00:00:23,000 --> 00:00:27,110 And using this class, we will create a new instance. 12 00:00:27,110 --> 00:00:29,900 Write a new instance object of this class. 13 00:00:29,900 --> 00:00:31,070 So let's call that uh. 14 00:00:31,070 --> 00:00:36,620 Let uh, let's call it BST is equal to new binary search tree. 15 00:00:37,700 --> 00:00:42,320 And then we will call the functions which we are going to write on this object. 16 00:00:42,320 --> 00:00:42,530 Right. 17 00:00:42,530 --> 00:00:46,520 So we will have BST dot insert for example 20. 18 00:00:47,270 --> 00:00:50,810 So this is the first part which is to write the insert function. 19 00:00:50,810 --> 00:00:51,170 Right. 20 00:00:51,170 --> 00:00:55,430 So we have to write the insert function the find function and the remove function. 21 00:00:55,430 --> 00:00:56,570 So let's get started. 22 00:00:56,570 --> 00:01:01,190 And over here I've just uh written this out over here so that we can visualize. 23 00:01:01,190 --> 00:01:03,110 It's easier to visualize like this right. 24 00:01:03,110 --> 00:01:04,580 So I have this over here. 25 00:01:04,580 --> 00:01:07,280 So using the insert function which we have we are going to write. 26 00:01:07,280 --> 00:01:09,440 We will create this binary search tree. 27 00:01:09,440 --> 00:01:10,910 Now let's get started. 28 00:01:11,210 --> 00:01:14,450 Now for the class node we will have the constructor. 29 00:01:14,450 --> 00:01:15,920 So let's write the constructor. 30 00:01:15,920 --> 00:01:18,890 And we need the value to be passed in over here. 31 00:01:19,830 --> 00:01:23,940 And we say that this dot value is equal to the value which we passed. 32 00:01:24,670 --> 00:01:28,090 And we say this dot left is equal to null. 33 00:01:29,070 --> 00:01:31,350 And this dot right is equal to null. 34 00:01:33,080 --> 00:01:37,250 So for each node initially, we will have the left and right pointing to null. 35 00:01:37,250 --> 00:01:41,990 And then when we call the insert function, we will place it at the correct place in the binary search 36 00:01:41,990 --> 00:01:45,230 tree, so that the binary search tree property is fulfilled. 37 00:01:45,410 --> 00:01:45,860 All right. 38 00:01:45,890 --> 00:01:50,510 Now let's go ahead and write the constructor for the binary search tree class over here. 39 00:01:50,690 --> 00:01:52,070 And we say. 40 00:01:53,100 --> 00:01:55,020 This dot root is equal to null. 41 00:01:55,020 --> 00:01:58,410 We are not passing any value, we just setting the root to be null. 42 00:01:58,470 --> 00:01:59,130 All right. 43 00:01:59,160 --> 00:02:02,490 Now over here we will write the instance method. 44 00:02:02,490 --> 00:02:04,080 So we'll have insert. 45 00:02:05,520 --> 00:02:07,410 And we will be passing the value. 46 00:02:08,210 --> 00:02:08,750 All right. 47 00:02:08,750 --> 00:02:11,990 And we will also write the find method. 48 00:02:12,200 --> 00:02:14,060 And again we will be passing the value. 49 00:02:14,060 --> 00:02:17,060 And it will either return the node or it will return false. 50 00:02:17,060 --> 00:02:19,880 If the value is not found in the binary search tree. 51 00:02:19,880 --> 00:02:25,340 And then finally we will write the remove function where again the value is passed and that particular 52 00:02:25,340 --> 00:02:27,590 node will be removed from the binary search tree. 53 00:02:27,620 --> 00:02:28,130 All right. 54 00:02:28,130 --> 00:02:30,290 So this is what we are going to do. 55 00:02:30,290 --> 00:02:32,930 Now let's get started with the insert function. 56 00:02:33,380 --> 00:02:38,570 Now initially let's say that we have this instance object over here we have BST. 57 00:02:38,570 --> 00:02:40,250 And this is empty initially. 58 00:02:40,250 --> 00:02:43,100 And let's say we are calling BST dot insert 20. 59 00:02:43,100 --> 00:02:44,540 So we come over here. 60 00:02:44,540 --> 00:02:47,840 And at this point the binary search tree is empty right. 61 00:02:47,840 --> 00:02:50,870 So we need to set this 20 as the root right. 62 00:02:50,870 --> 00:02:52,100 So the root is null. 63 00:02:52,100 --> 00:02:54,500 So we need to set the 20 as the root. 64 00:02:54,500 --> 00:02:55,820 So let's go ahead and do that. 65 00:02:55,820 --> 00:02:57,470 So first we say that. 66 00:02:58,500 --> 00:02:59,940 Uh, let's say const. 67 00:03:00,640 --> 00:03:01,600 New node. 68 00:03:02,800 --> 00:03:08,830 Or let's just call it node is equal to new node and we pass in the value. 69 00:03:11,330 --> 00:03:11,750 All right. 70 00:03:11,780 --> 00:03:14,420 Now we are going to check whether the root is null, right? 71 00:03:14,420 --> 00:03:19,730 If not this dot root, that means the root is null or the binary search tree is empty. 72 00:03:19,730 --> 00:03:25,250 If this is the case then we say this dot root is equal to node and we are done right. 73 00:03:25,250 --> 00:03:26,540 We can just return this. 74 00:03:26,540 --> 00:03:29,060 That is, we are returning the whole binary search tree. 75 00:03:29,360 --> 00:03:29,810 All right. 76 00:03:29,840 --> 00:03:35,960 Now if this is not the case we proceed further and we let's have a variable let's say tree. 77 00:03:35,960 --> 00:03:38,240 Let tree is equal to this dot root. 78 00:03:39,210 --> 00:03:43,320 Because we need to find the correct position right where to insert the particular node. 79 00:03:43,320 --> 00:03:44,760 So let's go ahead and check that. 80 00:03:44,760 --> 00:03:48,000 So over here we say that tree is the root at this point. 81 00:03:48,000 --> 00:03:50,940 And then we loop over the binary search tree. 82 00:03:51,180 --> 00:03:56,700 And let's say while true and at some instance at that is at the point where we have already found the 83 00:03:56,700 --> 00:04:00,330 correct place and inserted the node, we will exit from this while loop. 84 00:04:00,600 --> 00:04:01,050 All right. 85 00:04:01,080 --> 00:04:06,900 Now what we need to do is we need to check whether the value is less than the value of the node. 86 00:04:06,900 --> 00:04:09,540 So if value less than three dot value. 87 00:04:10,870 --> 00:04:11,200 Right. 88 00:04:11,200 --> 00:04:13,690 If this is the case, then we have to move left. 89 00:04:13,690 --> 00:04:14,140 Right. 90 00:04:14,140 --> 00:04:15,520 So we have to move left. 91 00:04:16,180 --> 00:04:17,740 So let's just write a comment. 92 00:04:17,740 --> 00:04:18,400 Move left. 93 00:04:18,430 --> 00:04:23,740 Now if this is not the case, if if this is not the case then what we do we move right? 94 00:04:25,510 --> 00:04:29,440 So that is how we find the right position where the node has to be inserted. 95 00:04:29,440 --> 00:04:29,800 Right. 96 00:04:29,800 --> 00:04:31,000 Let's take this example. 97 00:04:31,000 --> 00:04:35,410 Let's say we have already inserted 20 and let's say we are trying to insert six. 98 00:04:35,410 --> 00:04:40,600 Now we are over here, we see that six is less than this value 20 right. 99 00:04:40,600 --> 00:04:41,920 So we have to move left. 100 00:04:41,920 --> 00:04:46,840 Now let's say we have already inserted six and 35 and we are trying to insert 27 for example. 101 00:04:46,840 --> 00:04:49,240 So in this case we start again at the root. 102 00:04:49,240 --> 00:04:51,580 And we see that 27 is greater than 20. 103 00:04:51,580 --> 00:04:52,990 So we move right right. 104 00:04:52,990 --> 00:04:54,310 And then we have 35. 105 00:04:54,310 --> 00:04:56,560 We see that 27 is less than 35. 106 00:04:56,560 --> 00:04:58,810 So we move left and we find the place. 107 00:04:58,810 --> 00:05:01,870 So just imagine that at this point these are not inserted. 108 00:05:01,870 --> 00:05:03,280 So over here we will have null right. 109 00:05:03,280 --> 00:05:06,280 So if we find that this is null we can just insert it over here. 110 00:05:06,280 --> 00:05:08,320 So that is what we are going to write over here. 111 00:05:08,320 --> 00:05:09,340 So let's go ahead. 112 00:05:09,340 --> 00:05:12,520 So if value is less than three then we move left. 113 00:05:12,520 --> 00:05:18,100 So first we check whether the position at tree dot left is null. 114 00:05:18,100 --> 00:05:22,690 So if not tree dot left then we can just insert it over there. 115 00:05:22,690 --> 00:05:22,870 Right. 116 00:05:23,080 --> 00:05:23,890 We don't need to move. 117 00:05:23,890 --> 00:05:26,080 Actually we can just insert it over there. 118 00:05:26,080 --> 00:05:27,580 So let's write that. 119 00:05:27,580 --> 00:05:32,410 So in this case we can say tree dot left is equal to node. 120 00:05:32,770 --> 00:05:33,940 And then we are done. 121 00:05:33,940 --> 00:05:34,120 Right. 122 00:05:34,120 --> 00:05:36,910 We can just return the binary search tree and exit. 123 00:05:36,910 --> 00:05:39,040 But if that is not the case we move left. 124 00:05:39,040 --> 00:05:41,710 That is three is equal to three dot left. 125 00:05:42,940 --> 00:05:43,390 All right. 126 00:05:43,390 --> 00:05:45,040 So what happened over here? 127 00:05:45,040 --> 00:05:46,690 Just imagine this is not there right. 128 00:05:46,690 --> 00:05:48,520 Let me just write it like this. 129 00:05:48,520 --> 00:05:51,700 So if this is not there and we are trying to insert 27. 130 00:05:51,700 --> 00:05:54,460 So again we are at 20, we come to 35. 131 00:05:54,460 --> 00:05:56,950 And then we move left and we see that there is nothing over here. 132 00:05:56,950 --> 00:05:57,220 Right. 133 00:05:57,220 --> 00:05:58,930 So then we can just insert it over here. 134 00:05:58,930 --> 00:06:00,640 So that's what we have done over here. 135 00:06:00,640 --> 00:06:02,530 We have checked whether tree dot left is null. 136 00:06:02,530 --> 00:06:07,540 And if that is the case then we just assign the node to tree dot left right. 137 00:06:07,540 --> 00:06:11,650 Now if over here for example again 27 was there. 138 00:06:12,220 --> 00:06:14,950 And let's say we are trying to insert 25. 139 00:06:14,950 --> 00:06:17,170 So again we came to 35. 140 00:06:17,170 --> 00:06:18,430 Then we move left. 141 00:06:18,430 --> 00:06:22,300 And at this point right again we are at this point where we are 35. 142 00:06:22,630 --> 00:06:24,730 We are trying to match with the previous example, right. 143 00:06:24,730 --> 00:06:28,930 So we are at 35 and we see that we have to move in the left direction. 144 00:06:28,930 --> 00:06:29,920 But this is not null. 145 00:06:29,920 --> 00:06:30,910 So what do we do. 146 00:06:30,940 --> 00:06:33,250 We again move tree is equal to three dot left. 147 00:06:33,250 --> 00:06:36,070 So we come over here and then we check its left and right. 148 00:06:36,070 --> 00:06:37,450 So that's the procedure. 149 00:06:37,450 --> 00:06:37,960 All right. 150 00:06:37,960 --> 00:06:40,450 Now in the else case right. 151 00:06:40,450 --> 00:06:47,470 So this will happen when the value is greater than or equal to the value at tree right. 152 00:06:47,470 --> 00:06:48,520 So tree dot value. 153 00:06:48,520 --> 00:06:51,340 So that's the case which is the else part over here. 154 00:06:51,340 --> 00:06:54,040 So notice that it's not only greater it's also equal. 155 00:06:54,040 --> 00:06:58,570 For example in this tree in this example which I have written over here, you can see that we have three 156 00:06:58,570 --> 00:07:00,160 over here and we have three over here. 157 00:07:00,160 --> 00:07:02,230 So let's say we are trying to insert three. 158 00:07:02,650 --> 00:07:04,540 And so only this is not there. 159 00:07:04,540 --> 00:07:05,530 So I'm just removing this. 160 00:07:05,530 --> 00:07:07,510 So imagine over here we have null. 161 00:07:07,510 --> 00:07:09,400 So and we are trying to insert three. 162 00:07:09,400 --> 00:07:13,600 So we start again at the root and we move left because three is less than 20. 163 00:07:13,630 --> 00:07:15,760 We move left because three is less than six. 164 00:07:15,760 --> 00:07:16,750 And we are over here. 165 00:07:16,750 --> 00:07:20,140 Now we are checking whether three is less than three which is not true. 166 00:07:20,140 --> 00:07:20,470 Right. 167 00:07:20,470 --> 00:07:21,880 So it will not come over here. 168 00:07:21,880 --> 00:07:25,000 It will not come into this part, but it will come into the else part. 169 00:07:25,000 --> 00:07:27,340 And we see that its right is null. 170 00:07:27,340 --> 00:07:29,140 So we will just insert it over here. 171 00:07:29,140 --> 00:07:31,540 So that's what we are doing over here. 172 00:07:31,720 --> 00:07:32,140 All right. 173 00:07:32,140 --> 00:07:36,160 So if the value is greater than or equal to three dot value we either move right. 174 00:07:36,160 --> 00:07:39,100 Or if that position is null we insert it over there. 175 00:07:39,100 --> 00:07:39,610 All right. 176 00:07:39,610 --> 00:07:41,680 So let's check whether that position is null. 177 00:07:41,680 --> 00:07:43,810 So if not three dot right. 178 00:07:45,050 --> 00:07:47,000 In that case, we just insert it, right? 179 00:07:47,000 --> 00:07:51,050 So we can say tree dot right is equal to node and we are done. 180 00:07:51,050 --> 00:07:52,700 And we can just return this. 181 00:07:53,510 --> 00:07:54,050 All right. 182 00:07:54,080 --> 00:07:59,660 Now if this is not the case, if we don't have a null over here then we have to move in the right direction. 183 00:07:59,660 --> 00:08:02,240 And for this we do tree is equal to three dot. 184 00:08:02,690 --> 00:08:03,320 Right. 185 00:08:03,920 --> 00:08:04,310 All right. 186 00:08:04,310 --> 00:08:05,090 And we are done. 187 00:08:05,090 --> 00:08:06,920 We are done with the insert function. 188 00:08:08,350 --> 00:08:11,050 All right, so let me just clean this up a bit. 189 00:08:11,470 --> 00:08:12,190 Now. 190 00:08:13,100 --> 00:08:18,770 Let's go ahead and call the insert function to create this binary search tree, which I've written over 191 00:08:18,770 --> 00:08:18,920 here. 192 00:08:18,920 --> 00:08:19,100 Right. 193 00:08:19,100 --> 00:08:20,600 So let's just take it down. 194 00:08:23,300 --> 00:08:25,640 All right so that we can see it. 195 00:08:25,640 --> 00:08:26,810 So we have 20. 196 00:08:26,810 --> 00:08:31,040 So 123456789 ten 1112. 197 00:08:31,040 --> 00:08:32,840 So this is 12 elements. 198 00:08:32,840 --> 00:08:35,300 So let me just write this 12 times. 199 00:08:35,300 --> 00:08:36,350 So this is one. 200 00:08:37,250 --> 00:08:43,340 23456789 ten 1112. 201 00:08:43,370 --> 00:08:44,030 So 20. 202 00:08:44,060 --> 00:08:44,930 Then we have six. 203 00:08:44,930 --> 00:08:46,850 So let's quickly write that we have six. 204 00:08:46,850 --> 00:08:48,800 Then we have 35. 205 00:08:50,100 --> 00:08:51,810 Then we have three and eight. 206 00:08:54,270 --> 00:08:55,890 All right, so let's write eight. 207 00:08:56,850 --> 00:08:59,490 And then we have 27 and 55. 208 00:09:04,060 --> 00:09:05,860 And one three. 209 00:09:10,420 --> 00:09:12,640 And 2529. 210 00:09:17,910 --> 00:09:19,050 And 60. 211 00:09:21,320 --> 00:09:23,420 All right, so let's run this. 212 00:09:25,140 --> 00:09:28,260 And let's take a look at our binary search tree. 213 00:09:31,510 --> 00:09:31,900 All right. 214 00:09:31,900 --> 00:09:33,700 So this is the expectation right. 215 00:09:33,700 --> 00:09:35,560 So we have the expectation over here. 216 00:09:35,560 --> 00:09:36,790 So let's take a look. 217 00:09:36,790 --> 00:09:38,740 The root node is 20 which is correct. 218 00:09:38,980 --> 00:09:40,660 And on its left we have six. 219 00:09:40,660 --> 00:09:42,250 And on its right we have 35. 220 00:09:42,250 --> 00:09:42,640 All right. 221 00:09:42,640 --> 00:09:45,070 So it inserted in the correct position. 222 00:09:45,070 --> 00:09:47,830 And for six the children are three and eight which is correct. 223 00:09:47,830 --> 00:09:49,660 For three the children are one and three. 224 00:09:49,660 --> 00:09:51,040 Notice that three is on the right. 225 00:09:51,040 --> 00:09:52,660 Right as we have discussed. 226 00:09:52,660 --> 00:09:56,200 And for one it's null and null, and for three it's also null and null. 227 00:09:56,200 --> 00:09:57,700 So yes this is correct. 228 00:09:57,700 --> 00:10:00,040 And for eight again there are no children. 229 00:10:00,040 --> 00:10:00,730 So it's null. 230 00:10:00,730 --> 00:10:01,990 So this part is correct. 231 00:10:01,990 --> 00:10:03,130 Now what about this part. 232 00:10:03,130 --> 00:10:08,470 We have 35 over here and its children are 27 and 55 which is correct. 233 00:10:08,500 --> 00:10:12,130 Now the children of 27 are 25 and 29. 234 00:10:12,130 --> 00:10:13,810 And they don't have any children. 235 00:10:14,260 --> 00:10:14,590 All right. 236 00:10:14,590 --> 00:10:15,640 So this is correct. 237 00:10:15,640 --> 00:10:19,690 And then for 55 we have only one child, the right child which is 60. 238 00:10:19,690 --> 00:10:20,830 And the left child is null. 239 00:10:20,830 --> 00:10:21,730 So this is correct. 240 00:10:21,730 --> 00:10:22,090 Right. 241 00:10:22,090 --> 00:10:24,700 So we have successfully coded our insert function. 242 00:10:25,540 --> 00:10:25,990 All right. 243 00:10:25,990 --> 00:10:27,550 So this is pretty straightforward. 244 00:10:27,550 --> 00:10:30,580 Now let's go ahead and do the find function. 245 00:10:30,580 --> 00:10:32,770 This is also pretty similar to the insert function right. 246 00:10:32,770 --> 00:10:35,110 We have to just go to the correct position. 247 00:10:35,110 --> 00:10:37,330 And we have to see if the value is there or not. 248 00:10:37,330 --> 00:10:39,070 So let's go ahead and do that. 249 00:10:39,070 --> 00:10:41,770 Now again the value is passed over here. 250 00:10:41,770 --> 00:10:46,150 Now once inside this we have to check whether it's an empty binary search tree. 251 00:10:46,150 --> 00:10:47,080 So let's do that. 252 00:10:47,080 --> 00:10:48,940 If not this dot root. 253 00:10:49,940 --> 00:10:54,440 So that means that the binary search tree is empty and we can just return false. 254 00:10:54,440 --> 00:10:54,680 Right. 255 00:10:54,680 --> 00:10:57,200 So we won't be able to find anything over there. 256 00:10:57,200 --> 00:10:59,690 Now, if this is not the case, let's create a variable. 257 00:10:59,690 --> 00:11:01,520 Let tree is equal to this dot root. 258 00:11:01,520 --> 00:11:03,920 So we will start searching from the root. 259 00:11:03,920 --> 00:11:06,020 Now again we will keep looping. 260 00:11:07,030 --> 00:11:08,560 And now let me write Wild Tree. 261 00:11:08,560 --> 00:11:12,130 So as long as tree is not null, right, we will keep looping. 262 00:11:12,130 --> 00:11:17,680 As long as we are not reaching null for the node, we will keep looping and searching and we'll keep 263 00:11:17,680 --> 00:11:18,790 searching for the value. 264 00:11:18,790 --> 00:11:24,520 Now what we have to do is we have to see whether the past value is less than the node value, the value 265 00:11:24,520 --> 00:11:24,940 at the node. 266 00:11:24,940 --> 00:11:29,200 So let's say if if value less than three dot value. 267 00:11:30,080 --> 00:11:33,020 Now, if this is the case again, we have to move in the left direction, right? 268 00:11:33,050 --> 00:11:35,180 For example, if you are searching for three. 269 00:11:35,180 --> 00:11:37,610 So again we are at the root which is 20. 270 00:11:37,640 --> 00:11:39,050 Now three is less than 20. 271 00:11:39,050 --> 00:11:40,700 So we have to move in the left direction. 272 00:11:40,700 --> 00:11:41,990 Again three is less than six. 273 00:11:41,990 --> 00:11:44,630 So we have we have to move in the left direction and we find it right. 274 00:11:44,630 --> 00:11:48,050 So if value is less than three dot value then what do we do. 275 00:11:48,050 --> 00:11:49,610 We have to just move in the left direction. 276 00:11:49,610 --> 00:11:52,070 So three is equal to three dot left. 277 00:11:53,150 --> 00:11:53,600 All right. 278 00:11:53,630 --> 00:11:58,820 Now, if this is not the case, else if value is greater than three dot value. 279 00:12:00,510 --> 00:12:03,120 In this case, we have to just move in the right direction. 280 00:12:03,900 --> 00:12:06,420 P is equal to three dot, right? 281 00:12:06,870 --> 00:12:09,030 Finally, if we have found the value. 282 00:12:09,060 --> 00:12:13,590 Else if value is equal to three dot value. 283 00:12:14,270 --> 00:12:16,640 So in that, that means that we have found the node, right? 284 00:12:16,640 --> 00:12:22,490 The node with the required value has been found, and we can just return that particular node in that 285 00:12:22,490 --> 00:12:23,180 instance. 286 00:12:23,180 --> 00:12:28,910 And then finally, if we are out of the while loop and we have not found anything as mentioned in the 287 00:12:28,910 --> 00:12:33,530 question, we will just return false and we are done with our find function. 288 00:12:33,530 --> 00:12:35,750 So let's go ahead and test it out. 289 00:12:40,760 --> 00:12:41,990 And we get the node. 290 00:12:41,990 --> 00:12:42,350 All right. 291 00:12:42,350 --> 00:12:42,950 So it's working. 292 00:12:42,950 --> 00:12:44,900 So we got that particular node right. 293 00:12:44,900 --> 00:12:48,080 And it's left and right are pointing to null which is also correct. 294 00:12:48,080 --> 00:12:49,670 Right which we have visualized over here. 295 00:12:49,670 --> 00:12:51,710 Now let's try 35. 296 00:12:57,070 --> 00:13:02,380 And we get the node 35 and it's left is 27 and its right is 55, which is correct. 297 00:13:02,380 --> 00:13:04,720 So yes, our find function is also working. 298 00:13:04,720 --> 00:13:08,380 Now let's proceed and go ahead and write the remove function. 299 00:13:09,040 --> 00:13:09,310 All right. 300 00:13:09,310 --> 00:13:10,780 So I'm just clearing the console. 301 00:13:10,780 --> 00:13:13,750 Now over here we have the remove function. 302 00:13:13,750 --> 00:13:15,790 Let me just clear this space. 303 00:13:17,140 --> 00:13:18,730 Now in the remove function. 304 00:13:18,730 --> 00:13:24,310 Also, the way we go about this is that, as we have discussed in the previous video, there are three 305 00:13:24,460 --> 00:13:26,140 particular cases right now. 306 00:13:26,140 --> 00:13:35,260 If the node to be removed has two children, then we have to find the lowest value in the right subtree. 307 00:13:35,260 --> 00:13:37,750 Or we could find the highest value in the left subtree. 308 00:13:37,750 --> 00:13:39,340 So either one of these ways works. 309 00:13:39,340 --> 00:13:43,600 So over here we will go ahead and find the lowest value in the right subtree. 310 00:13:43,600 --> 00:13:45,220 So that's how we will remove it. 311 00:13:45,220 --> 00:13:49,090 And if it's just a leaf node we can just replace it with null. 312 00:13:49,090 --> 00:13:54,910 And if it's a node with only one child then we can just connect the parent with that particular child. 313 00:13:54,910 --> 00:13:58,240 So we have discussed these cases in the previous video. 314 00:13:58,240 --> 00:14:01,180 Now over here let's go ahead and implement this function. 315 00:14:01,570 --> 00:14:05,170 And before this again let's write um function. 316 00:14:05,170 --> 00:14:06,700 We will also need a helper function. 317 00:14:06,700 --> 00:14:08,800 So I'm just making a placeholder for it. 318 00:14:08,800 --> 00:14:10,210 So let's say get min. 319 00:14:10,210 --> 00:14:14,470 And over here we will pass a particular node right. 320 00:14:14,470 --> 00:14:16,240 So we'll pass a particular node. 321 00:14:16,240 --> 00:14:20,050 And then we want to that node will be treated as the root. 322 00:14:20,050 --> 00:14:20,350 Right. 323 00:14:20,350 --> 00:14:23,710 So it's a subtree actually with the root as this particular node. 324 00:14:23,710 --> 00:14:26,800 And in that subtree we want to find the minimum value right. 325 00:14:26,800 --> 00:14:31,810 Because we will use this when we want to find the minimum value in the right subtree of that particular 326 00:14:31,810 --> 00:14:33,580 node, which has to be deleted. 327 00:14:33,580 --> 00:14:36,400 And for the case where that node has two children. 328 00:14:36,400 --> 00:14:36,910 All right. 329 00:14:36,910 --> 00:14:39,640 So over here I'm just having it as a placeholder. 330 00:14:39,640 --> 00:14:42,400 We will come back and write this function when we need it. 331 00:14:42,400 --> 00:14:44,860 Now let's get started with the remove function. 332 00:14:45,310 --> 00:14:48,220 Now over here I've written that we are passing the value. 333 00:14:48,220 --> 00:14:53,050 Let me add two more things over here that we are going to pass to this function. 334 00:14:53,050 --> 00:14:57,040 So we will add the current node and we will add the parent node over here. 335 00:14:57,040 --> 00:14:58,600 Now why are we doing this. 336 00:14:58,600 --> 00:15:00,850 For example let me just explain that over here. 337 00:15:00,850 --> 00:15:03,040 Let's say we are trying to remove 35. 338 00:15:03,040 --> 00:15:03,580 All right. 339 00:15:03,580 --> 00:15:11,290 So we know that the lowest or let's say we are trying to remove 20 now in this if we are removing 20 340 00:15:11,320 --> 00:15:16,660 the lowest node in this right subtree right is 25, right. 341 00:15:16,660 --> 00:15:18,130 The lowest value is 25. 342 00:15:18,130 --> 00:15:20,530 So we have to put 25 over here. 343 00:15:20,530 --> 00:15:21,880 So I'm just doing that over here. 344 00:15:21,880 --> 00:15:23,530 I have to put 25 over here. 345 00:15:23,530 --> 00:15:25,900 And then I have to remove this right. 346 00:15:25,900 --> 00:15:27,130 I have to make this null. 347 00:15:27,700 --> 00:15:30,610 So what we will do is so I'm just putting it back. 348 00:15:30,610 --> 00:15:31,690 So this is 25. 349 00:15:31,690 --> 00:15:37,780 So what we will do is we will find the minimum value which is 25, using the get min node for this case 350 00:15:37,780 --> 00:15:39,010 where there are two children. 351 00:15:39,010 --> 00:15:40,570 And we will put that over here. 352 00:15:40,570 --> 00:15:43,840 Initially this was 20 and we changed this to 25. 353 00:15:43,840 --> 00:15:50,140 And then we will again call the remove function one more time recursively on this subtree. 354 00:15:50,140 --> 00:15:52,780 And we will pass 35 as the node right. 355 00:15:52,780 --> 00:15:55,870 So and then we will pass 25 as the value. 356 00:15:55,870 --> 00:15:57,850 Earlier we had passed the value as 20. 357 00:15:57,850 --> 00:16:00,910 But now we just need to change this 25 to null right. 358 00:16:00,910 --> 00:16:05,290 So to be able to do this in a recursive manner, that's why I'm writing this over here. 359 00:16:05,290 --> 00:16:06,160 Current and parent. 360 00:16:06,160 --> 00:16:06,400 Right. 361 00:16:06,400 --> 00:16:10,750 So initially when nothing is passed we will take current as the root node. 362 00:16:10,750 --> 00:16:13,300 So let's write this dot root over here. 363 00:16:13,300 --> 00:16:17,440 And the parent will be null because the parent of the root node is null. 364 00:16:18,100 --> 00:16:24,100 Now now when we call this recursively for example again I am writing 20 over here so that this is the 365 00:16:24,100 --> 00:16:24,850 binary search tree. 366 00:16:24,850 --> 00:16:29,590 And this is 25 right now when we want to remove this 20 right. 367 00:16:29,590 --> 00:16:31,330 We put this 25 over here. 368 00:16:31,330 --> 00:16:38,770 And we will recursively call the remove function this function over here on this subtree which has 35 369 00:16:38,770 --> 00:16:40,780 as the node and as the root. 370 00:16:40,780 --> 00:16:42,700 And these are the other nodes. 371 00:16:42,700 --> 00:16:42,880 Right. 372 00:16:42,880 --> 00:16:46,450 So in this case we will pass 35 as the current node. 373 00:16:46,450 --> 00:16:50,110 And the parent of 35 is 25 at this point. 374 00:16:50,110 --> 00:16:53,440 So again we will revisit this once more when we write this. 375 00:16:53,440 --> 00:16:55,180 So for now let me put this back. 376 00:16:55,180 --> 00:16:57,370 Put this back to 20 and let's proceed. 377 00:16:57,370 --> 00:17:00,880 So we have the remove function and it has three parameters passed to it. 378 00:17:00,880 --> 00:17:03,850 Value the current node and the parent of the current node. 379 00:17:03,850 --> 00:17:04,720 At this point. 380 00:17:04,720 --> 00:17:09,880 Initially the current is the root and the parent is null because the parent of the the the root node 381 00:17:09,880 --> 00:17:11,500 does not have any parent. 382 00:17:11,500 --> 00:17:11,980 All right. 383 00:17:11,980 --> 00:17:13,240 So let's go ahead. 384 00:17:13,690 --> 00:17:18,910 Now what we have to do is first we check whether again as we did in the other cases, whether the binary 385 00:17:18,910 --> 00:17:20,440 search tree is empty or not. 386 00:17:20,440 --> 00:17:24,580 So if not this dot root then we cannot remove anything from it. 387 00:17:24,580 --> 00:17:25,030 Right. 388 00:17:25,030 --> 00:17:28,930 So in that case we just oops. 389 00:17:28,930 --> 00:17:29,440 Yeah. 390 00:17:29,440 --> 00:17:35,350 If not this dot root, in that case we just return false because we cannot remove anything from it. 391 00:17:35,350 --> 00:17:35,830 All right. 392 00:17:35,830 --> 00:17:37,990 So we just come out of the loop. 393 00:17:37,990 --> 00:17:39,160 Now let's proceed. 394 00:17:39,160 --> 00:17:43,390 Now we have to loop through while current node is true. 395 00:17:43,390 --> 00:17:43,780 All right. 396 00:17:43,780 --> 00:17:45,040 So this is the current node. 397 00:17:45,580 --> 00:17:48,400 And then we will break out of this loop. 398 00:17:48,400 --> 00:17:51,370 At some point we will discuss this as we go ahead. 399 00:17:51,370 --> 00:17:55,210 Now first we need to find the node which has to be removed. 400 00:17:55,210 --> 00:17:55,390 Right. 401 00:17:55,390 --> 00:17:57,310 So that's the first thing that we are going to do. 402 00:17:57,310 --> 00:17:58,900 So let's look at the value. 403 00:17:58,900 --> 00:18:06,670 So if value less than current dot value in that case we just need to move in the left direction right. 404 00:18:06,670 --> 00:18:07,960 So let's write that. 405 00:18:07,960 --> 00:18:13,180 So moving in the left direction means we are setting the parent as the current node. 406 00:18:13,890 --> 00:18:17,310 And we are setting the current node as current dot left. 407 00:18:18,410 --> 00:18:18,740 Right. 408 00:18:18,740 --> 00:18:20,810 So we had current over here. 409 00:18:20,810 --> 00:18:23,390 We see that the value of current is less. 410 00:18:23,870 --> 00:18:26,120 Uh, the value is less than the value of the current node. 411 00:18:26,120 --> 00:18:27,890 So we have to move in the left direction. 412 00:18:27,890 --> 00:18:29,420 So that's why we do this. 413 00:18:29,420 --> 00:18:30,920 Current is equal to current dot left. 414 00:18:30,920 --> 00:18:33,290 But we don't want to miss the value of the parent. 415 00:18:33,290 --> 00:18:33,470 Right. 416 00:18:33,470 --> 00:18:37,760 Because we need to make some connections in some cases from the parent to the child etc.. 417 00:18:37,760 --> 00:18:38,000 Right. 418 00:18:38,000 --> 00:18:39,590 So we need to keep track of the parent. 419 00:18:39,590 --> 00:18:43,040 So when we move the current to current dot left the parent becomes current. 420 00:18:43,040 --> 00:18:44,600 So that's what we have done over here. 421 00:18:44,930 --> 00:18:45,380 All right. 422 00:18:45,380 --> 00:18:46,760 Now let's proceed. 423 00:18:46,760 --> 00:18:48,260 If this is not the case right. 424 00:18:48,260 --> 00:18:50,840 So let's write that else if. 425 00:18:51,700 --> 00:18:53,350 If the value is greater. 426 00:18:54,070 --> 00:18:56,350 Value is greater than current dot value. 427 00:18:58,450 --> 00:19:00,160 In this case, what do we do? 428 00:19:00,190 --> 00:19:01,630 We have to move in the right direction. 429 00:19:01,630 --> 00:19:05,110 So again it's similar to what we've written above. 430 00:19:05,110 --> 00:19:08,800 So the parent is set to current and the current is set to. 431 00:19:09,690 --> 00:19:10,530 Current dot, right? 432 00:19:11,800 --> 00:19:13,390 And we move in the right direction. 433 00:19:14,140 --> 00:19:14,680 All right. 434 00:19:14,680 --> 00:19:21,760 So again finally, if this is also not true, else means we have found the node to be deleted. 435 00:19:24,440 --> 00:19:25,160 All right. 436 00:19:26,930 --> 00:19:28,130 Now let's proceed. 437 00:19:28,160 --> 00:19:30,950 Now there are three cases as we discussed. 438 00:19:30,950 --> 00:19:31,160 Right. 439 00:19:31,160 --> 00:19:37,520 So there is a possibility that the node to be deleted has two children or it has one child or it has 440 00:19:37,520 --> 00:19:38,300 zero children. 441 00:19:38,300 --> 00:19:40,070 So let's think in that direction. 442 00:19:40,070 --> 00:19:43,370 So first we deal with the case where the node to be deleted. 443 00:19:44,710 --> 00:19:45,790 Has two children. 444 00:19:47,670 --> 00:19:49,680 So let's deal with that case first. 445 00:19:49,710 --> 00:19:51,600 Now, if this is the case, what? 446 00:19:51,600 --> 00:19:53,010 How can we identify it? 447 00:19:53,040 --> 00:19:58,500 We can check whether the current node has a left child and a right child. 448 00:19:58,500 --> 00:19:58,830 Right. 449 00:19:58,830 --> 00:20:02,130 So current dot left should not be null. 450 00:20:03,390 --> 00:20:04,200 And. 451 00:20:05,070 --> 00:20:06,420 Current dot, right? 452 00:20:07,640 --> 00:20:08,600 Should not be null. 453 00:20:10,410 --> 00:20:14,580 This means that the node which is to be deleted has two children. 454 00:20:14,580 --> 00:20:14,940 Right? 455 00:20:14,940 --> 00:20:16,680 So what do we do in this case? 456 00:20:17,160 --> 00:20:22,500 In this case we have to find for example, let's say we are again trying to remove this node over here, 457 00:20:22,500 --> 00:20:23,340 which is 20. 458 00:20:23,370 --> 00:20:26,820 We have to find the minimum value in the right subtree right. 459 00:20:26,820 --> 00:20:29,370 So the right subtree starts with 35. 460 00:20:29,370 --> 00:20:32,700 And then you have 2755 and 2529 and 60. 461 00:20:32,700 --> 00:20:34,560 So the minimum over here is 25. 462 00:20:34,560 --> 00:20:39,630 So we need to find that value and change the value of the current node to that value. 463 00:20:39,630 --> 00:20:39,930 Right. 464 00:20:39,930 --> 00:20:41,820 So we need to put this 25 over here. 465 00:20:41,820 --> 00:20:43,860 So we have discussed that right in the previous video. 466 00:20:43,860 --> 00:20:45,930 So let's look at the code to do this. 467 00:20:45,930 --> 00:20:47,850 So we say current node. 468 00:20:50,240 --> 00:20:55,160 Dot value is equal to the value that we return from this function. 469 00:20:55,340 --> 00:20:58,640 This is the help of helper function which we will call at this point. 470 00:20:58,640 --> 00:21:00,110 So we say this dot. 471 00:21:01,040 --> 00:21:06,560 Get mean, and then we have to pass the right. 472 00:21:07,450 --> 00:21:08,680 Uh, node of this, right? 473 00:21:08,680 --> 00:21:13,960 The current node is, for example, at 20 we need to find the minimum in the right subtree. 474 00:21:13,960 --> 00:21:16,300 So the right subtree starts at 35. 475 00:21:16,300 --> 00:21:18,910 So we have to pass this particular node over here. 476 00:21:18,910 --> 00:21:21,880 So this will be current dot right. 477 00:21:23,970 --> 00:21:24,300 All right. 478 00:21:24,300 --> 00:21:29,760 So we are passing current or right to this, uh, function so that it will return the minimum value. 479 00:21:29,760 --> 00:21:33,300 So let's at this point go ahead and write the helper function over here. 480 00:21:34,330 --> 00:21:36,640 Now, what is the helper function supposed to do? 481 00:21:36,670 --> 00:21:37,720 It has to go. 482 00:21:37,750 --> 00:21:42,670 It has to continuously, in an iterative manner, go left and left till it reaches null. 483 00:21:42,700 --> 00:21:43,060 Right. 484 00:21:43,060 --> 00:21:44,620 So let's write that over here. 485 00:21:44,620 --> 00:21:46,930 So we have know the node. 486 00:21:46,930 --> 00:21:50,200 This 35 for example in our example is passed over here. 487 00:21:50,200 --> 00:21:55,600 Right now we are going to loop while node dot left. 488 00:21:56,110 --> 00:21:58,720 So while node dot left is not null right. 489 00:21:58,720 --> 00:21:59,650 So let's just write it. 490 00:21:59,650 --> 00:22:03,310 So as long as it is not null we'll just move in the left direction. 491 00:22:03,310 --> 00:22:06,280 So we say node is equal to node dot left. 492 00:22:07,000 --> 00:22:11,560 Now when we come out of this while loop we will have reached node dot left is null right. 493 00:22:11,560 --> 00:22:16,300 So we are at the leftmost position of the right subtree which is the lowest value. 494 00:22:16,300 --> 00:22:20,680 At this point we just need to return the value return node dot value. 495 00:22:20,680 --> 00:22:21,430 And that's it. 496 00:22:21,430 --> 00:22:22,690 That's the helper function. 497 00:22:22,690 --> 00:22:25,240 So when we called our helper function over here. 498 00:22:26,190 --> 00:22:26,460 All right. 499 00:22:26,460 --> 00:22:27,360 So this is wrong. 500 00:22:27,360 --> 00:22:27,690 Yeah. 501 00:22:27,690 --> 00:22:32,850 So when we call the helper function over here, it will find the minimum value in the right subtree 502 00:22:32,850 --> 00:22:34,350 and return it right. 503 00:22:34,350 --> 00:22:36,360 Because we we are returning that value over here. 504 00:22:36,360 --> 00:22:39,510 And that value will be assigned to current dot value. 505 00:22:39,510 --> 00:22:45,030 So for example over here if you are trying to delete 20 the minimum value in the right subtree, which 506 00:22:45,030 --> 00:22:47,010 is this part over here is 25. 507 00:22:47,010 --> 00:22:52,740 So we find it the helper function will return 25 and we will set this value as 25. 508 00:22:52,740 --> 00:22:55,260 Now what do we need to do next. 509 00:22:55,260 --> 00:22:56,400 We need to remove this right. 510 00:22:56,400 --> 00:22:57,690 We have to set this to null. 511 00:22:57,690 --> 00:23:02,460 So for this we will recursively call the same remove function right. 512 00:23:02,460 --> 00:23:04,020 So let's go ahead and do that. 513 00:23:04,440 --> 00:23:09,090 But at this point we will pass the current node and the parent node right. 514 00:23:09,090 --> 00:23:10,770 So that's the that's the difference. 515 00:23:10,770 --> 00:23:12,210 That's what we discussed over here. 516 00:23:12,210 --> 00:23:14,250 That that's the reason we are passing. 517 00:23:14,250 --> 00:23:17,100 We are having these parameters for the remove function. 518 00:23:17,100 --> 00:23:18,930 So let's go ahead and do that. 519 00:23:18,930 --> 00:23:19,860 This dot remove. 520 00:23:19,860 --> 00:23:21,660 So let's write that it will be over here. 521 00:23:21,660 --> 00:23:23,280 So this dot remove. 522 00:23:23,700 --> 00:23:26,400 And then what is the value that we want to remove. 523 00:23:26,400 --> 00:23:28,500 It will be the current value at this point. 524 00:23:28,500 --> 00:23:28,650 Right. 525 00:23:28,650 --> 00:23:29,730 Which is this 25. 526 00:23:29,730 --> 00:23:30,780 It's not 20. 527 00:23:30,810 --> 00:23:33,510 We have removed 20 by putting 25 over here. 528 00:23:33,510 --> 00:23:36,420 Now we just want to remove 25 right. 529 00:23:36,420 --> 00:23:43,020 So the value which I pass over here is current dot value which is 25 at this case for our example. 530 00:23:43,020 --> 00:23:48,180 And then we will pass the current node and the parent of the current node. 531 00:23:48,180 --> 00:23:53,820 So current node let's dot write right current node dot right. 532 00:23:54,810 --> 00:24:00,210 That's the first note in the right subtree, and the parent of this node is the current node. 533 00:24:01,110 --> 00:24:01,920 Right or current. 534 00:24:01,920 --> 00:24:03,120 We call it current over here. 535 00:24:03,150 --> 00:24:03,630 All right. 536 00:24:03,630 --> 00:24:09,300 So what this will do is it will recursively call the remove function on this right subtree. 537 00:24:09,300 --> 00:24:11,010 It will search for 25. 538 00:24:11,010 --> 00:24:12,990 And it will see that 25 is over here. 539 00:24:12,990 --> 00:24:14,940 And it will replace this with null. 540 00:24:14,970 --> 00:24:16,980 Now let's look at one more case. 541 00:24:17,520 --> 00:24:21,090 Let's say for example over here 25 was not the ending. 542 00:24:21,090 --> 00:24:24,300 And you have a right child for 25. 543 00:24:24,300 --> 00:24:25,920 Let's say that's 26. 544 00:24:25,920 --> 00:24:26,730 So is that correct? 545 00:24:26,730 --> 00:24:28,740 26 when we enter it's less than 35. 546 00:24:28,740 --> 00:24:29,520 It will come over here. 547 00:24:29,520 --> 00:24:31,230 27 it's less than 27. 548 00:24:31,230 --> 00:24:31,800 It comes over here. 549 00:24:31,800 --> 00:24:33,120 It's greater than 25. 550 00:24:33,120 --> 00:24:33,990 So it comes to the right. 551 00:24:33,990 --> 00:24:36,030 So yes it would be inserted over here. 552 00:24:36,990 --> 00:24:39,180 I'm just making this correct. 553 00:24:39,180 --> 00:24:39,600 All right. 554 00:24:39,600 --> 00:24:41,280 So what would happen in this case. 555 00:24:41,280 --> 00:24:43,770 Again we found 25 as the minimum value. 556 00:24:43,800 --> 00:24:45,030 We placed it over here. 557 00:24:45,030 --> 00:24:46,290 This was earlier 20. 558 00:24:46,320 --> 00:24:52,710 Now when we recursively call the remove function on this right subtree this part right it will find 559 00:24:52,710 --> 00:24:53,580 25. 560 00:24:53,580 --> 00:24:57,480 And then it will make this connection 27 and 26 will be connected. 561 00:24:57,480 --> 00:25:01,410 So this 25 will go and we will have 26 over here. 562 00:25:02,250 --> 00:25:02,580 All right. 563 00:25:02,580 --> 00:25:05,730 So we have discussed this in the concept video also. 564 00:25:05,730 --> 00:25:06,120 All right. 565 00:25:06,120 --> 00:25:10,950 So for this that's why we are calling the remove function over here recursively. 566 00:25:10,950 --> 00:25:12,990 And that's what is happening over here. 567 00:25:12,990 --> 00:25:17,490 Now when we do the code walkthrough let's again visit this so that you are very thorough with what with 568 00:25:17,490 --> 00:25:18,630 what is happening over here. 569 00:25:19,470 --> 00:25:20,070 All right. 570 00:25:20,070 --> 00:25:25,110 So we have dealt the case where the node to be deleted has two children. 571 00:25:25,110 --> 00:25:26,370 And that is over with this. 572 00:25:26,370 --> 00:25:27,930 Now let's proceed. 573 00:25:27,930 --> 00:25:32,310 The next case that we have to look at is if we are deleting the root node. 574 00:25:36,540 --> 00:25:40,830 Now, why are we treating this as a separate case? 575 00:25:40,830 --> 00:25:42,900 Because over here there is no parent, right? 576 00:25:42,900 --> 00:25:46,920 So that is one point when you're deleting the root node, there is no connection with the parent of 577 00:25:46,920 --> 00:25:48,180 that node that you have to make. 578 00:25:48,180 --> 00:25:53,940 Secondly, if the binary search tree has only one node and that node is the root node and we are trying 579 00:25:53,940 --> 00:25:56,880 to delete it, then we have to set the root to null. 580 00:25:56,880 --> 00:25:58,980 So these are the two points to be kept in mind. 581 00:25:58,980 --> 00:26:00,120 So let's proceed. 582 00:26:00,120 --> 00:26:02,160 Now how do we check this. 583 00:26:02,160 --> 00:26:04,050 Else if parent is equal to. 584 00:26:05,110 --> 00:26:05,740 Null. 585 00:26:06,430 --> 00:26:12,310 This is the case where we are trying to delete the root node, and the root node does not have two children. 586 00:26:12,310 --> 00:26:17,290 So we are also aware of that because if the root node had two children it would come over here. 587 00:26:17,290 --> 00:26:17,530 Right. 588 00:26:17,530 --> 00:26:19,750 So that would have taken care over here. 589 00:26:19,750 --> 00:26:22,810 So over here we are checking whether we are deleting the root node. 590 00:26:22,810 --> 00:26:25,390 And it does not have uh two children. 591 00:26:25,390 --> 00:26:25,690 All right. 592 00:26:25,690 --> 00:26:26,680 So let's proceed. 593 00:26:27,130 --> 00:26:32,170 Now if this is the case, first we check whether it, it has, let's say a left child. 594 00:26:32,170 --> 00:26:33,940 We could do it in either order. 595 00:26:33,940 --> 00:26:35,890 So let's say current dot left. 596 00:26:37,400 --> 00:26:39,020 Not equal to null. 597 00:26:39,020 --> 00:26:41,870 So that means there is a left child, right? 598 00:26:41,870 --> 00:26:47,000 So we have to make that left child as the root node in this case. 599 00:26:47,000 --> 00:26:50,630 And again remember it does not have a right child if it is having a left child. 600 00:26:50,630 --> 00:26:55,310 If you are reaching over here, it does not have a right child because if it had two children, we already 601 00:26:55,310 --> 00:26:56,780 have taken care of it over here. 602 00:26:56,780 --> 00:27:01,280 So again remember this is if it has one child and that's the left child. 603 00:27:01,280 --> 00:27:07,520 So if that is the case, what do we do then we have to set the the root as the left child. 604 00:27:07,520 --> 00:27:08,270 So let's go ahead. 605 00:27:08,270 --> 00:27:12,710 So current dot value has to be the value of the left child right. 606 00:27:14,020 --> 00:27:19,750 So current dot left dot value and then the left child. 607 00:27:19,750 --> 00:27:23,890 If it has a left and right connection, that connection has to be made to the current node. 608 00:27:23,890 --> 00:27:24,100 Right. 609 00:27:24,100 --> 00:27:32,560 So we say current dot left is equal to current dot left dot left. 610 00:27:34,480 --> 00:27:36,550 And we can say current dot, right? 611 00:27:38,790 --> 00:27:43,260 Is equal to current dot left, dot right. 612 00:27:43,260 --> 00:27:44,580 So what's happening over here? 613 00:27:44,580 --> 00:27:46,110 Let's try to visualize this. 614 00:27:46,110 --> 00:27:49,050 Let's say our tree looks like this. 615 00:27:49,050 --> 00:27:51,480 For example we have 20. 616 00:27:51,480 --> 00:27:56,850 Let's again put this 20 over here which is the example which we have taken. 617 00:27:56,850 --> 00:28:00,600 And let me just modify this a little bit for our example. 618 00:28:00,600 --> 00:28:02,280 I'm just removing 35 over here. 619 00:28:02,280 --> 00:28:04,710 I'm just keeping it over here so that I can keep it back. 620 00:28:04,710 --> 00:28:04,920 Right. 621 00:28:04,920 --> 00:28:08,250 So we are just using this example to look at various scenarios. 622 00:28:08,250 --> 00:28:10,950 Let's say our binary search tree looks like this. 623 00:28:10,950 --> 00:28:12,660 We have 20 and we have six. 624 00:28:12,660 --> 00:28:14,280 And we are trying to remove 20. 625 00:28:14,280 --> 00:28:16,800 So this node over here is the root node. 626 00:28:16,800 --> 00:28:18,090 It does not have two children. 627 00:28:18,090 --> 00:28:19,620 So it will not come over here. 628 00:28:19,620 --> 00:28:22,710 And we are over here now we are over here. 629 00:28:22,710 --> 00:28:24,270 We see that it's the parent node. 630 00:28:24,270 --> 00:28:24,750 Yes. 631 00:28:24,750 --> 00:28:27,930 And we see that the left child is not null. 632 00:28:27,930 --> 00:28:29,790 So we have six over here. 633 00:28:29,790 --> 00:28:34,320 Now in this case again let me just modify this a little bit. 634 00:28:34,320 --> 00:28:37,890 Let's put three and eight also over here for clarity's sake. 635 00:28:37,890 --> 00:28:40,200 And I'm just removing these also. 636 00:28:42,980 --> 00:28:43,250 All right. 637 00:28:43,250 --> 00:28:46,730 So let's say this is the binary search tree which we have at this point. 638 00:28:46,730 --> 00:28:49,640 Now if you are trying to remove 20, what do we need to do. 639 00:28:49,670 --> 00:28:51,440 We have to put this six over here. 640 00:28:51,440 --> 00:28:52,010 Right. 641 00:28:52,010 --> 00:28:56,750 And then this node should be connected to this three and eight. 642 00:28:56,960 --> 00:28:58,010 There's nothing over here. 643 00:28:58,010 --> 00:28:58,280 Right. 644 00:28:58,280 --> 00:28:59,960 So I can just remove this. 645 00:29:00,110 --> 00:29:03,470 Let me just take it to the right because I want to bring this back. 646 00:29:03,470 --> 00:29:04,760 So there's nothing over here. 647 00:29:04,760 --> 00:29:05,030 Right. 648 00:29:05,030 --> 00:29:07,580 So after we do the deletion what should happen. 649 00:29:07,580 --> 00:29:09,110 We should get six over here. 650 00:29:09,110 --> 00:29:11,810 And we should have three and eight. 651 00:29:12,570 --> 00:29:13,440 As its children. 652 00:29:13,440 --> 00:29:13,770 Right. 653 00:29:13,770 --> 00:29:16,260 So over here we should have three. 654 00:29:16,620 --> 00:29:18,720 And over here we should have eight. 655 00:29:19,080 --> 00:29:21,240 And that should be the right child. 656 00:29:21,240 --> 00:29:21,420 Right. 657 00:29:21,420 --> 00:29:23,010 So it should look like this. 658 00:29:26,390 --> 00:29:26,960 All right. 659 00:29:26,960 --> 00:29:28,700 So that is what we are trying to do over here. 660 00:29:28,700 --> 00:29:29,030 Right. 661 00:29:29,030 --> 00:29:32,330 So we are setting the value of the current node as the value of the left node. 662 00:29:32,330 --> 00:29:38,540 And this left and this right is set to the left and right of the current dot left node. 663 00:29:38,960 --> 00:29:44,180 So current dot left is a node and its right is set to the right of current node, and its left is set 664 00:29:44,180 --> 00:29:45,440 to the left of the current node. 665 00:29:45,440 --> 00:29:46,820 That is what we are doing over here. 666 00:29:46,820 --> 00:29:52,460 So let me just undo these changes so that we have our example over here intact for other cases also. 667 00:29:53,820 --> 00:29:54,570 All right. 668 00:29:57,550 --> 00:29:58,960 Now let's proceed. 669 00:30:00,390 --> 00:30:02,220 Now, if this is not the case, right? 670 00:30:02,220 --> 00:30:04,050 If this is not the case, let's proceed. 671 00:30:04,050 --> 00:30:04,830 Else if. 672 00:30:06,050 --> 00:30:09,710 And let's say we say that we see that it has a right child. 673 00:30:09,710 --> 00:30:11,480 So if current dot right. 674 00:30:12,340 --> 00:30:14,170 Is not equal to null. 675 00:30:14,830 --> 00:30:15,820 It's similar. 676 00:30:15,820 --> 00:30:16,330 Similar right. 677 00:30:16,330 --> 00:30:19,090 In this in this case we have to just set current dot value. 678 00:30:20,630 --> 00:30:25,220 Is equal to the value of the right child, which is current dot right dot value. 679 00:30:25,940 --> 00:30:28,340 And we have to say it's left and right. 680 00:30:28,340 --> 00:30:31,820 That is current dot left and current dot right. 681 00:30:33,870 --> 00:30:36,570 Has to be set to the left and right of the right node. 682 00:30:36,570 --> 00:30:38,220 So we have current dot. 683 00:30:39,250 --> 00:30:41,590 Right, which is the child which is existing. 684 00:30:41,590 --> 00:30:41,980 Right. 685 00:30:41,980 --> 00:30:45,340 So let me just write this over here for conceptual clarity. 686 00:30:45,340 --> 00:30:47,590 Again, over here also we have current dot right. 687 00:30:47,590 --> 00:30:53,560 And now the left child of the current node has to be set to the left child of current dot right. 688 00:30:53,560 --> 00:30:54,820 So dot left over here. 689 00:30:54,820 --> 00:31:00,250 Similarly the right child of current has to be set to the right child of current dot right. 690 00:31:00,250 --> 00:31:02,830 So this is current dot right dot right. 691 00:31:03,670 --> 00:31:04,330 All right. 692 00:31:04,330 --> 00:31:05,950 So we have covered these cases. 693 00:31:05,950 --> 00:31:08,830 So this is the case where we are trying to delete the root node. 694 00:31:08,830 --> 00:31:10,510 And it has one child right. 695 00:31:10,510 --> 00:31:15,100 So the one child which each it has if it's the left node we do this. 696 00:31:15,100 --> 00:31:17,740 If the child which is there is the right node we do this. 697 00:31:17,740 --> 00:31:21,550 Now there is one more case which is the else part. 698 00:31:21,580 --> 00:31:25,150 This means that this is just a single node tree. 699 00:31:27,410 --> 00:31:29,180 Single node binary search tree. 700 00:31:29,180 --> 00:31:31,100 And we are trying to remove the root. 701 00:31:31,100 --> 00:31:31,340 Right. 702 00:31:31,340 --> 00:31:32,570 So we are removing the root. 703 00:31:32,570 --> 00:31:36,740 In this case we have to say this dot root is equal to null. 704 00:31:38,100 --> 00:31:38,790 All right. 705 00:31:38,790 --> 00:31:42,210 So we are done with the case where we are trying to remove the. 706 00:31:43,310 --> 00:31:43,910 Root node. 707 00:31:43,910 --> 00:31:44,210 Right. 708 00:31:44,210 --> 00:31:49,850 And we have also taken care of this special case where if it's a single node and we are trying to remove 709 00:31:49,850 --> 00:31:53,030 the root itself, we have to set the root to null. 710 00:31:53,060 --> 00:31:59,990 Now let's check the case where the node which is to be removed either has zero children or one child. 711 00:32:00,020 --> 00:32:01,940 Now there are two possibilities. 712 00:32:01,940 --> 00:32:07,460 That particular node which is to be removed, can either be the left child of the parent or the right 713 00:32:07,460 --> 00:32:08,240 child of the parent. 714 00:32:08,240 --> 00:32:09,740 So let's check that else. 715 00:32:09,740 --> 00:32:13,700 If current node is equal to parent dot left. 716 00:32:14,700 --> 00:32:16,320 In this case we do something. 717 00:32:16,320 --> 00:32:18,720 So let's just write placeholders for now. 718 00:32:18,720 --> 00:32:20,040 Or else if. 719 00:32:21,230 --> 00:32:24,620 The current node is the parent node, right? 720 00:32:24,650 --> 00:32:26,210 The right child of the parent. 721 00:32:26,750 --> 00:32:28,430 And in this case also we do something. 722 00:32:28,430 --> 00:32:29,960 So let's discuss this now. 723 00:32:29,960 --> 00:32:32,810 For example over here I have 55. 724 00:32:32,810 --> 00:32:35,150 Let's say 55 is the node which is to be removed. 725 00:32:35,150 --> 00:32:37,610 Now 55 is the right child of the parent. 726 00:32:37,610 --> 00:32:37,970 Right. 727 00:32:37,970 --> 00:32:42,500 So in this case we have to say parent dot right is equal to this 60 over here. 728 00:32:42,500 --> 00:32:45,950 Similarly let's for example remove this 29 for now. 729 00:32:45,950 --> 00:32:48,680 And again 27 has only one child 25. 730 00:32:48,680 --> 00:32:51,050 So let's say we are trying to remove 27. 731 00:32:51,050 --> 00:32:56,300 In this case 35 is the parent and its left has to be set to 25. 732 00:32:56,300 --> 00:32:56,660 Right. 733 00:32:56,660 --> 00:33:02,600 So that's why we need to know whether the node which is to be removed in 27 and 55, the two examples 734 00:33:02,600 --> 00:33:06,140 which we discussed is a left child or a right child of the parent. 735 00:33:06,140 --> 00:33:08,270 So that is what we are checking over here. 736 00:33:08,720 --> 00:33:13,730 Now if it's a left child then we set parent dot left right. 737 00:33:16,210 --> 00:33:17,980 Is equal to the child. 738 00:33:17,980 --> 00:33:22,330 Now we are saying that it either has one child or zero children, right? 739 00:33:22,330 --> 00:33:28,000 So if it has one child, whichever that child is, whether it's a left child or a right child of current. 740 00:33:28,000 --> 00:33:28,900 We said that. 741 00:33:28,900 --> 00:33:29,110 Right. 742 00:33:29,110 --> 00:33:31,180 So parent dot left should be that node. 743 00:33:31,180 --> 00:33:32,290 So let's check it. 744 00:33:32,290 --> 00:33:36,190 And if it's if it does not have any children parent dot left will be equal to null. 745 00:33:36,190 --> 00:33:38,080 So that is what we are trying to write over here. 746 00:33:38,080 --> 00:33:42,880 So let's check whether current dot left is not null. 747 00:33:44,000 --> 00:33:48,530 If it's not null, then we we put current dot left. 748 00:33:48,530 --> 00:33:51,200 That parent dot left should connect to current dot left. 749 00:33:53,450 --> 00:33:57,320 Now, if it is null, if it is null, then the other child, right? 750 00:33:57,320 --> 00:33:58,850 So current dot right. 751 00:33:58,850 --> 00:34:05,240 Now in case both of these are null, in case current dot left is null, either current or right could 752 00:34:05,240 --> 00:34:07,070 be a child node or it can be null. 753 00:34:07,070 --> 00:34:08,450 So that's fine right? 754 00:34:08,450 --> 00:34:12,080 So if there is no children then parent dot left has to be set to null anyway. 755 00:34:12,080 --> 00:34:13,130 So this is correct. 756 00:34:13,130 --> 00:34:18,890 Similarly over here also because we find that the current node is the right child of the parent, we 757 00:34:18,890 --> 00:34:20,540 have to say parent dot, right. 758 00:34:22,790 --> 00:34:23,660 Is equal to. 759 00:34:23,690 --> 00:34:25,640 So we just check whether there is any child. 760 00:34:25,640 --> 00:34:27,020 So the same thing can be done. 761 00:34:27,020 --> 00:34:29,900 Current dot left not equal to null. 762 00:34:31,020 --> 00:34:36,750 That means if there is a left child then we have to do parent dot right is equal to current dot left. 763 00:34:36,780 --> 00:34:41,010 Now if that is not the case, then parent dot right is equal to current dot right? 764 00:34:41,010 --> 00:34:45,480 So if there is a child that child would be assigned that node will be connected to parent dot. 765 00:34:45,480 --> 00:34:45,900 Right. 766 00:34:45,900 --> 00:34:48,540 And if there is no child parent dot right will be null. 767 00:34:48,540 --> 00:34:50,160 And then we are done with this. 768 00:34:50,160 --> 00:34:53,790 Now at this point we have to break out of the while loop. 769 00:34:53,790 --> 00:34:55,620 So let's just write that. 770 00:34:59,520 --> 00:35:01,170 So we write break. 771 00:35:01,650 --> 00:35:02,850 So what does this mean. 772 00:35:02,850 --> 00:35:05,640 So we have come to this else part right. 773 00:35:05,640 --> 00:35:09,150 That means we have found the value which is to be deleted. 774 00:35:09,150 --> 00:35:09,540 Right. 775 00:35:09,540 --> 00:35:14,130 So once we are inside, any one of these will be executed. 776 00:35:14,130 --> 00:35:14,310 Right. 777 00:35:14,310 --> 00:35:16,200 Because we have found the value to be deleted. 778 00:35:16,200 --> 00:35:20,460 So by by reaching over here, we have to come out of this loop. 779 00:35:20,460 --> 00:35:24,120 We don't need to keep again repeating with that particular current node. 780 00:35:24,120 --> 00:35:27,480 Because if you don't write this then this would be an infinite loop, right? 781 00:35:27,480 --> 00:35:29,640 Because current is now some node, right? 782 00:35:29,640 --> 00:35:31,890 So current is still true. 783 00:35:31,890 --> 00:35:33,210 So this will never end. 784 00:35:33,210 --> 00:35:37,200 So once we are done with the removal which is this part over here, right. 785 00:35:37,200 --> 00:35:39,570 Else means we have found the node to be deleted. 786 00:35:39,570 --> 00:35:43,140 So inside we go ahead and do the deletion and we break out of it. 787 00:35:43,230 --> 00:35:43,740 All right. 788 00:35:43,740 --> 00:35:44,580 So we are done. 789 00:35:44,580 --> 00:35:48,240 And at this point at the end we just return the binary search tree. 790 00:35:48,240 --> 00:35:50,760 So return this and we are done. 791 00:35:50,760 --> 00:35:52,410 Let's go ahead and test our code. 792 00:35:52,410 --> 00:35:54,570 So we have our binary search tree. 793 00:35:54,570 --> 00:35:56,580 So this is the binary search tree which we have. 794 00:35:56,580 --> 00:35:59,790 Now let's try to take one case of each. 795 00:35:59,790 --> 00:36:03,270 We are trying to let's try to remove a node which has one child. 796 00:36:03,270 --> 00:36:07,590 And let's try to remove a node which has two children and a node which has no children. 797 00:36:07,590 --> 00:36:09,150 So let's go ahead and do that. 798 00:36:09,150 --> 00:36:13,830 So first let's just remove 60 over here which is a leaf node. 799 00:36:15,690 --> 00:36:16,020 All right. 800 00:36:16,020 --> 00:36:17,520 So this 60 should have gone. 801 00:36:17,520 --> 00:36:20,880 So 55 should just have no children at this point. 802 00:36:20,880 --> 00:36:23,580 So let's go in this branch which is 35. 803 00:36:23,580 --> 00:36:24,030 Right. 804 00:36:24,030 --> 00:36:26,670 So 35 2755. 805 00:36:26,670 --> 00:36:28,830 And then 55 has no children. 806 00:36:28,830 --> 00:36:30,090 So this is working. 807 00:36:30,090 --> 00:36:30,600 All right. 808 00:36:30,600 --> 00:36:31,890 So let's proceed. 809 00:36:32,340 --> 00:36:34,170 And we have removed 60 at this point. 810 00:36:34,170 --> 00:36:39,270 Now let's go ahead and remove 29 so that I can make 27 a node with only one child. 811 00:36:39,270 --> 00:36:41,790 So let's just remove 29. 812 00:36:44,530 --> 00:36:44,890 All right. 813 00:36:44,890 --> 00:36:46,720 So let's look at the binary search tree. 814 00:36:46,720 --> 00:36:47,890 Now we have 20. 815 00:36:47,890 --> 00:36:52,720 And over here we have 3537 has 2755. 816 00:36:52,720 --> 00:36:57,100 And what about 2727 has only one child which is. 817 00:36:58,610 --> 00:36:59,330 25. 818 00:36:59,330 --> 00:36:59,540 Right. 819 00:36:59,540 --> 00:37:00,860 The left node is 25. 820 00:37:00,860 --> 00:37:01,850 The right node is null. 821 00:37:01,850 --> 00:37:02,720 So this is correct. 822 00:37:02,720 --> 00:37:03,200 All right. 823 00:37:03,200 --> 00:37:04,550 So let's proceed now. 824 00:37:04,550 --> 00:37:07,310 Now we have removed 29 also. 825 00:37:07,310 --> 00:37:09,500 Now we're just going to remove 27. 826 00:37:09,500 --> 00:37:11,600 And this is a node which has only one child. 827 00:37:11,600 --> 00:37:12,650 So this should be working. 828 00:37:12,650 --> 00:37:13,910 So let's check that. 829 00:37:16,500 --> 00:37:17,010 All right. 830 00:37:17,010 --> 00:37:18,330 So we have removed 27. 831 00:37:18,330 --> 00:37:19,710 Our expectation is 35. 832 00:37:19,710 --> 00:37:22,740 Should have now two children 25 and 55. 833 00:37:22,740 --> 00:37:28,980 So let's check that 20 then 3535 has two children 25 and 55 which is correct. 834 00:37:28,980 --> 00:37:32,130 Five now let's say we want to remove 20. 835 00:37:32,130 --> 00:37:33,570 So 20 has two children. 836 00:37:33,570 --> 00:37:34,920 So let's do that case. 837 00:37:36,990 --> 00:37:38,550 Now what is the expectation? 838 00:37:38,550 --> 00:37:44,730 This is the right subtree 35 2555 so the expectation is this 25 should be made the root. 839 00:37:44,730 --> 00:37:47,100 And then this should be removed from here. 840 00:37:47,100 --> 00:37:47,310 Right. 841 00:37:47,310 --> 00:37:48,600 So that's the expectation. 842 00:37:48,600 --> 00:37:50,340 So let's go ahead and look at it. 843 00:37:50,340 --> 00:37:54,210 Now when we run this we can see yes this 25 is the root now. 844 00:37:54,210 --> 00:37:56,610 So we have 25 over here which is correct. 845 00:37:56,610 --> 00:37:58,470 And then this 25 should be removed. 846 00:37:58,470 --> 00:37:58,680 Right. 847 00:37:58,680 --> 00:38:00,030 So let's just remove it over here. 848 00:38:00,030 --> 00:38:03,990 And the children should be 35 and 55. 849 00:38:03,990 --> 00:38:05,580 The child of 35 is 55. 850 00:38:05,580 --> 00:38:09,510 So let's check it 25 has two children six and 35 which is correct. 851 00:38:09,510 --> 00:38:15,150 And 35 has only the right child, which is 55, 55 has no children. 852 00:38:15,150 --> 00:38:16,770 So yes, that's also working. 853 00:38:17,250 --> 00:38:17,670 All right. 854 00:38:17,670 --> 00:38:19,560 So yes, our code is working. 855 00:38:19,560 --> 00:38:24,930 Now let's take a few samples and walk through the code that we have written to analyze it better and 856 00:38:24,930 --> 00:38:25,650 understand it. 857 00:38:25,650 --> 00:38:30,270 And we will also quickly relook at the complexity analysis of this solution.