1 00:00:00,580 --> 00:00:01,570 Welcome back. 2 00:00:01,570 --> 00:00:04,480 So we have successfully coded our binary search tree. 3 00:00:04,510 --> 00:00:08,500 We have designed it and we have written the insert remove and find functions. 4 00:00:08,500 --> 00:00:12,970 Now let's take a few samples and walk through the code to understand it deeper. 5 00:00:12,970 --> 00:00:17,680 And again we will also look at the time complexity and space complexity of our solution. 6 00:00:17,680 --> 00:00:18,190 All right. 7 00:00:18,190 --> 00:00:20,380 So we start with the insert function over here. 8 00:00:20,380 --> 00:00:22,090 Now what is happening over here. 9 00:00:22,090 --> 00:00:24,430 We are calling uh the insert function. 10 00:00:24,430 --> 00:00:27,070 Let's say we have called it and a value has been passed to it. 11 00:00:27,070 --> 00:00:28,180 Let's start from there. 12 00:00:28,180 --> 00:00:31,720 So let's say this is the existing binary search tree at this point. 13 00:00:31,720 --> 00:00:36,550 And let's say for example we are inserting the value uh 75. 14 00:00:36,550 --> 00:00:36,850 All right. 15 00:00:36,850 --> 00:00:39,070 So let's say we are inserting the value 75. 16 00:00:39,070 --> 00:00:40,330 Now what's happening. 17 00:00:40,750 --> 00:00:41,740 We come over here. 18 00:00:41,740 --> 00:00:43,690 Now we create a node right. 19 00:00:43,690 --> 00:00:45,700 So only the value 75 is passed. 20 00:00:45,700 --> 00:00:49,720 So at this point we create the nodes with value 75. 21 00:00:49,720 --> 00:00:51,790 Then we check whether the root is null. 22 00:00:51,790 --> 00:00:52,810 So the root is not null. 23 00:00:52,810 --> 00:00:55,000 So this is not an empty binary search tree. 24 00:00:55,000 --> 00:00:58,960 If it was then this 75 would have been set as the root over here. 25 00:00:58,960 --> 00:00:59,440 Right? 26 00:00:59,440 --> 00:01:05,260 Then we have a variable tree over here which is initialized to the root right. 27 00:01:05,260 --> 00:01:09,460 And then we keep looping till we break out of this while loop. 28 00:01:09,460 --> 00:01:14,170 So this while loop over here is ending right where it's ending over here. 29 00:01:14,770 --> 00:01:17,470 So we keep looping it over in this while loop. 30 00:01:17,470 --> 00:01:22,480 Now we are going to check whether the value which is 75 is less than three dot value. 31 00:01:22,480 --> 00:01:24,790 So the value over here is 76. 32 00:01:24,790 --> 00:01:28,930 And we see that 75 yes indeed is less than 76. 33 00:01:28,930 --> 00:01:29,980 So what do we do. 34 00:01:30,010 --> 00:01:32,200 We move in the left direction right. 35 00:01:32,200 --> 00:01:36,940 So first we are going to check whether the left child of this node over here is null. 36 00:01:36,940 --> 00:01:38,830 So that's what we are checking over here. 37 00:01:38,830 --> 00:01:40,510 If tree dot left is null. 38 00:01:40,510 --> 00:01:43,120 So if that is the case then we just insert it over here. 39 00:01:43,120 --> 00:01:44,800 But if that is and then we return. 40 00:01:44,800 --> 00:01:46,210 So we come out of the while loop. 41 00:01:46,210 --> 00:01:49,000 And if that is not the case so what do we do. 42 00:01:49,000 --> 00:01:50,800 We say tree is equal to three dot left. 43 00:01:50,800 --> 00:01:54,010 So now initially tree was pointing to this node. 44 00:01:54,010 --> 00:01:56,410 Now tree is pointing to this node over here. 45 00:01:56,410 --> 00:01:58,870 And again it doesn't go to the else right. 46 00:01:58,870 --> 00:01:59,950 It doesn't go to the else. 47 00:01:59,950 --> 00:02:01,540 And we come back we loop. 48 00:02:01,540 --> 00:02:02,290 It's still true. 49 00:02:02,290 --> 00:02:03,760 So again we check the value. 50 00:02:03,760 --> 00:02:05,740 Now value 75. 51 00:02:05,740 --> 00:02:09,700 Is it less than three dot value three dot value is 50 in this case. 52 00:02:09,700 --> 00:02:10,900 So it's not less. 53 00:02:10,900 --> 00:02:12,940 So it does not go to the if loop over here. 54 00:02:12,940 --> 00:02:14,560 And then it comes to the else loop. 55 00:02:14,560 --> 00:02:16,720 So in the else loop we are checking. 56 00:02:16,720 --> 00:02:20,290 We know that 75 has to be greater than or equal to 50. 57 00:02:20,290 --> 00:02:20,500 Right. 58 00:02:20,500 --> 00:02:21,820 So that's what is true. 59 00:02:21,820 --> 00:02:26,710 Now we just check whether the right child of 50 is null. 60 00:02:26,710 --> 00:02:29,380 So and in this case we see that it is null. 61 00:02:29,380 --> 00:02:31,120 So if not tree dot right. 62 00:02:31,120 --> 00:02:32,170 So that's it is null. 63 00:02:32,170 --> 00:02:35,920 So it will come inside and we will say tree dot right is equal to node. 64 00:02:35,920 --> 00:02:38,110 So this node over here will be placed over here. 65 00:02:38,110 --> 00:02:40,180 So tree dot right is equal to node. 66 00:02:40,180 --> 00:02:43,060 And that's how we successfully insert the node over here. 67 00:02:43,060 --> 00:02:49,450 And we have seen that the time complexity of this solution is O of log n in the case of a balanced tree. 68 00:02:49,450 --> 00:02:54,160 And the worst case will be o of n in the case of an unbalanced tree. 69 00:02:54,160 --> 00:02:56,410 If it were looking something like this, right. 70 00:02:56,410 --> 00:02:58,120 So in this case it's balanced. 71 00:02:58,120 --> 00:03:00,640 So the time complexity will be O of log n. 72 00:03:00,640 --> 00:03:04,090 And you can see that we are not doing we are not using any extra space. 73 00:03:04,090 --> 00:03:04,480 Right. 74 00:03:04,480 --> 00:03:05,560 We are not creating. 75 00:03:05,560 --> 00:03:08,590 We are not having any recursive calls on the call stack as well. 76 00:03:08,590 --> 00:03:12,070 So the space complexity of this solution is O of one. 77 00:03:12,310 --> 00:03:12,730 All right. 78 00:03:12,760 --> 00:03:15,460 Now let's proceed to the find function. 79 00:03:15,460 --> 00:03:17,380 So this is the find function that we have written. 80 00:03:17,380 --> 00:03:19,690 And we have a binary search tree over here. 81 00:03:19,690 --> 00:03:22,690 Let's say we are trying to find the value 90. 82 00:03:23,380 --> 00:03:23,860 All right. 83 00:03:23,860 --> 00:03:24,880 So what do we do. 84 00:03:24,910 --> 00:03:28,120 We pass the value 90 over here and we are inside the function. 85 00:03:28,120 --> 00:03:31,270 Now we are checking whether the binary search tree is empty. 86 00:03:31,300 --> 00:03:36,460 If it's empty then we can just return false because we won't be able to find anything in an empty binary 87 00:03:36,460 --> 00:03:37,030 search tree. 88 00:03:37,030 --> 00:03:39,280 Now, if it's not false, we come over here. 89 00:03:39,280 --> 00:03:39,580 Right? 90 00:03:39,580 --> 00:03:41,710 So that means the binary search tree is not empty. 91 00:03:41,740 --> 00:03:44,680 Now we have a variable tree which is pointing to the root. 92 00:03:44,680 --> 00:03:47,020 So tree is pointing to the root at this point. 93 00:03:47,020 --> 00:03:49,150 Now we are going to loop through. 94 00:03:49,150 --> 00:03:53,200 As long as this variable is not becoming null right. 95 00:03:53,200 --> 00:03:58,060 So it will become null if we have searched through the entire tree and we have not found anything. 96 00:03:58,060 --> 00:04:03,010 Let's also take a case where we are searching for 91, so we will see how we break out of the while 97 00:04:03,010 --> 00:04:03,970 loop in this case. 98 00:04:03,970 --> 00:04:09,790 Now we are checking whether value which is 90 is whether it is less than three dot value. 99 00:04:09,790 --> 00:04:11,830 In this case three dot value is 76. 100 00:04:11,830 --> 00:04:13,300 So this is not true right? 101 00:04:13,300 --> 00:04:14,020 This is not true. 102 00:04:14,020 --> 00:04:15,400 So we come to the else part. 103 00:04:15,400 --> 00:04:18,730 And over here we are checking whether the value is greater than three dot value. 104 00:04:18,730 --> 00:04:21,160 So yes 90 is greater than 76. 105 00:04:21,160 --> 00:04:22,210 So what do we do. 106 00:04:22,240 --> 00:04:24,160 We say three is equal to three dot right. 107 00:04:24,160 --> 00:04:27,280 So we have three pointing to 80 at this point. 108 00:04:27,280 --> 00:04:27,730 All right. 109 00:04:27,730 --> 00:04:30,790 Now again it's still true right. 110 00:04:30,790 --> 00:04:33,490 So the tree is still having a node. 111 00:04:33,490 --> 00:04:36,970 So again we come to the while loop and we again come into it. 112 00:04:36,970 --> 00:04:37,990 We loop through it again. 113 00:04:37,990 --> 00:04:42,220 Now we are checking whether the value which is 70 uh 90 right. 114 00:04:42,220 --> 00:04:43,330 The value is 90. 115 00:04:43,360 --> 00:04:46,480 Is it less than three dot value which is not the case. 116 00:04:46,480 --> 00:04:46,750 Right. 117 00:04:46,750 --> 00:04:48,250 So again we come to the else part. 118 00:04:48,280 --> 00:04:50,350 We see that 90 is greater than 80. 119 00:04:50,350 --> 00:04:52,210 So again we move in the right direction. 120 00:04:52,210 --> 00:04:56,710 So tree is now pointing to this node over here because we moved in the right direction. 121 00:04:56,710 --> 00:04:57,220 All right. 122 00:04:57,220 --> 00:04:59,560 So again tree is truthy right. 123 00:04:59,560 --> 00:04:59,890 It's true. 124 00:05:00,140 --> 00:05:00,440 Still. 125 00:05:00,440 --> 00:05:02,120 So again we loop through in. 126 00:05:02,150 --> 00:05:05,810 We again come to the while loop and we check whether the value 90. 127 00:05:05,810 --> 00:05:10,160 In this case it's the value is 93, dot value is 90 and value is 90. 128 00:05:10,160 --> 00:05:12,080 So is 90 less than 90. 129 00:05:12,080 --> 00:05:12,650 No. 130 00:05:12,650 --> 00:05:14,360 Is 90 greater than 90. 131 00:05:14,360 --> 00:05:14,600 No. 132 00:05:14,600 --> 00:05:17,690 So we come to the else if the third elseif over here. 133 00:05:17,690 --> 00:05:21,470 And now at this case value is equal to the value right. 134 00:05:21,470 --> 00:05:22,790 So these two are equal. 135 00:05:22,790 --> 00:05:24,500 Therefore we return the tree. 136 00:05:24,500 --> 00:05:26,360 That means we return this node. 137 00:05:26,360 --> 00:05:29,840 So we have found the node which we are looking for. 138 00:05:29,840 --> 00:05:32,630 And we return that particular tree and we come out. 139 00:05:32,630 --> 00:05:33,680 So that's it. 140 00:05:33,680 --> 00:05:35,720 So that's how the find function works. 141 00:05:35,720 --> 00:05:38,210 Now let's say we were looking for 91 right. 142 00:05:38,210 --> 00:05:41,960 So let's say we have reached till 90 and we were looking for 91. 143 00:05:41,960 --> 00:05:43,400 Let me just delete this. 144 00:05:43,400 --> 00:05:44,330 Remove this okay. 145 00:05:44,330 --> 00:05:46,550 So let's say we were looking for 91. 146 00:05:46,550 --> 00:05:50,570 And similar to the case where we were searching for 90 we have reached till 90. 147 00:05:50,600 --> 00:05:54,110 Now again we check the it's still truthy right. 148 00:05:54,110 --> 00:05:56,840 The tree root is still this is still a valid node. 149 00:05:56,840 --> 00:05:58,070 So this is truthy. 150 00:05:58,070 --> 00:06:00,110 So again we come into the while loop. 151 00:06:00,110 --> 00:06:00,650 Right. 152 00:06:00,650 --> 00:06:01,820 Let me just clear this up. 153 00:06:01,820 --> 00:06:07,250 And then we check whether the value which is 91 is it less than 90. 154 00:06:07,280 --> 00:06:07,850 No. 155 00:06:07,850 --> 00:06:08,120 Right. 156 00:06:08,120 --> 00:06:08,870 So no. 157 00:06:08,870 --> 00:06:10,790 So we don't go inside over here. 158 00:06:10,790 --> 00:06:14,510 Then we check whether 91 is greater than 90 which is over here. 159 00:06:14,510 --> 00:06:15,320 Which is true. 160 00:06:15,320 --> 00:06:15,590 Right. 161 00:06:15,590 --> 00:06:18,350 So in this case we move in the right direction. 162 00:06:18,350 --> 00:06:19,940 So tree is equal to three dot right. 163 00:06:19,940 --> 00:06:23,120 So 3.3. right in this case is null right. 164 00:06:23,120 --> 00:06:25,370 So now tree is pointing to null. 165 00:06:25,370 --> 00:06:29,930 And then we come out and again when we check now tree is null right. 166 00:06:29,930 --> 00:06:31,130 So null is falsey. 167 00:06:31,130 --> 00:06:34,550 So we come out of the while loop and we just return false. 168 00:06:34,550 --> 00:06:39,920 Which means that the there is no node in this binary search tree with value 91. 169 00:06:39,920 --> 00:06:46,700 And again the time complexity of this solution is O of log n best and average, because that would be 170 00:06:46,700 --> 00:06:47,930 the height, right? 171 00:06:47,930 --> 00:06:49,490 If the tree is balanced. 172 00:06:49,490 --> 00:06:55,040 And that's the number of comparisons we have to make to find or to be sure that that particular node 173 00:06:55,040 --> 00:06:56,870 is not there in the binary search tree. 174 00:06:56,870 --> 00:07:00,650 And the worst case will be O of n if it looks like a linked list, right. 175 00:07:00,650 --> 00:07:01,430 Something like this. 176 00:07:01,430 --> 00:07:06,890 If it's an unbalanced, uh, uh, binary search tree, and the space complexity over here you can see 177 00:07:06,890 --> 00:07:07,670 is O of one. 178 00:07:07,670 --> 00:07:12,260 We are not making any recursive calls on the call stack and we are not using any extra space. 179 00:07:12,380 --> 00:07:14,870 Now finally let's look at the remove function. 180 00:07:14,870 --> 00:07:17,030 So this is the remove function which we have written. 181 00:07:17,480 --> 00:07:19,730 Now it's a lengthy part right. 182 00:07:19,730 --> 00:07:21,320 So we have the remove function over here. 183 00:07:21,320 --> 00:07:23,510 And this is the get min function which we have written. 184 00:07:23,510 --> 00:07:26,690 And we have a uh sample binary search tree over here. 185 00:07:26,690 --> 00:07:33,680 Now let's say we want to remove let's take one case each where let's start with the case where we want 186 00:07:33,680 --> 00:07:35,750 to remove a node which has two children. 187 00:07:35,750 --> 00:07:37,880 For example, let's say we want to remove 80. 188 00:07:38,860 --> 00:07:39,400 All right. 189 00:07:39,400 --> 00:07:40,420 So we want to remove 80. 190 00:07:40,420 --> 00:07:41,590 So we are over here. 191 00:07:41,590 --> 00:07:43,030 We pass the value 80. 192 00:07:43,030 --> 00:07:46,270 And initially when we call this we don't pass current and parent. 193 00:07:46,270 --> 00:07:47,440 So current is the root. 194 00:07:47,440 --> 00:07:50,290 So this is the current at this point. 195 00:07:50,290 --> 00:07:53,080 And the parent is null initially. 196 00:07:53,080 --> 00:07:53,440 Right. 197 00:07:53,440 --> 00:07:54,970 So we are initializing this over here. 198 00:07:54,970 --> 00:07:57,130 Parent is null and current is this dot root. 199 00:07:57,160 --> 00:08:01,870 Now we come inside we check whether the binary search tree is empty which is not the case. 200 00:08:01,870 --> 00:08:03,190 So we come inside. 201 00:08:03,190 --> 00:08:06,970 Now while current so current is truthy at this point because it's a valid node right. 202 00:08:06,970 --> 00:08:08,620 So we are inside this while loop. 203 00:08:08,620 --> 00:08:10,540 Now we are checking the value. 204 00:08:10,540 --> 00:08:12,460 Value is 80 right. 205 00:08:13,000 --> 00:08:14,500 Which is what we are passing over here. 206 00:08:14,500 --> 00:08:17,650 We are checking whether 80 is less than current dot value. 207 00:08:17,650 --> 00:08:19,030 Current dot value is 76. 208 00:08:19,030 --> 00:08:20,320 This is not true right. 209 00:08:20,320 --> 00:08:22,600 So we don't go inside this if loop. 210 00:08:22,600 --> 00:08:27,130 Then we come over here we are checking whether value is greater than current dot value 80 is greater 211 00:08:27,130 --> 00:08:28,840 than 76 which is true. 212 00:08:28,840 --> 00:08:32,080 So we come inside this loop right inside this condition. 213 00:08:32,080 --> 00:08:34,000 And then we set parent is equal to current. 214 00:08:34,000 --> 00:08:36,340 So we make parent equal to 76. 215 00:08:37,020 --> 00:08:39,270 And we say current is current dot right, right. 216 00:08:39,270 --> 00:08:40,350 So what do we do. 217 00:08:40,350 --> 00:08:41,430 We current was this. 218 00:08:41,430 --> 00:08:43,230 So we just say current is current dot right. 219 00:08:43,230 --> 00:08:45,330 So current will be 80 at this point. 220 00:08:45,330 --> 00:08:46,080 All right. 221 00:08:46,500 --> 00:08:47,880 Now what do we do. 222 00:08:48,150 --> 00:08:48,660 Again. 223 00:08:48,660 --> 00:08:51,720 We have done this operation so we don't go into the LS. 224 00:08:51,720 --> 00:08:53,460 So the LS ends over here again. 225 00:08:53,460 --> 00:08:56,460 We come over here now current is still truthy right. 226 00:08:56,460 --> 00:08:57,450 This is a valid node. 227 00:08:57,450 --> 00:09:01,380 So again we check whether the value is less than current dot value. 228 00:09:01,380 --> 00:09:04,290 And in this case that's not the case right 80 and 80. 229 00:09:04,290 --> 00:09:05,880 So 80 is not less than 80. 230 00:09:05,880 --> 00:09:07,680 So it does not come over here. 231 00:09:07,680 --> 00:09:10,590 Then we check whether 80 is greater than 80 which is not true. 232 00:09:10,590 --> 00:09:11,640 So we don't come over here. 233 00:09:11,640 --> 00:09:16,080 So we come to the else part, which means that we have found the node which is to be deleted, which 234 00:09:16,080 --> 00:09:18,630 is this particular node, the current node at this point. 235 00:09:18,630 --> 00:09:19,140 All right. 236 00:09:19,140 --> 00:09:20,100 So let's proceed. 237 00:09:20,100 --> 00:09:23,610 Now we start with the case where there are two children. 238 00:09:23,610 --> 00:09:23,910 Right. 239 00:09:23,910 --> 00:09:27,300 So over here we are checking whether current dot left is not null. 240 00:09:27,300 --> 00:09:29,520 And current dot right is not null which is the case. 241 00:09:29,520 --> 00:09:33,420 So we know that it has two children and we come inside over here. 242 00:09:33,840 --> 00:09:37,350 Now we say current dot value is equal to this dot get mean. 243 00:09:37,350 --> 00:09:39,120 And then we pass current dot right. 244 00:09:39,120 --> 00:09:40,410 So we pass 90. 245 00:09:40,410 --> 00:09:45,330 And so in this right subtree and in this right subtree there is just one node right. 246 00:09:45,330 --> 00:09:48,150 So we just get the minimum value which is 90 itself. 247 00:09:48,150 --> 00:09:50,340 So this function over here get min. 248 00:09:50,340 --> 00:09:54,630 And where we are passing the node we will just keep going left and left till it reaches the minimum 249 00:09:54,630 --> 00:09:54,840 value. 250 00:09:54,840 --> 00:10:00,330 So if there was something over here let's say let's say we had um something greater than 80 which is 251 00:10:00,330 --> 00:10:01,950 82 but less than 90. 252 00:10:01,950 --> 00:10:03,150 So let's say we had 82. 253 00:10:03,180 --> 00:10:06,240 Then the get min function would have returned 82. 254 00:10:06,240 --> 00:10:06,630 All right. 255 00:10:06,630 --> 00:10:08,880 So in this case it's going to return 90. 256 00:10:08,880 --> 00:10:09,990 And what do we do. 257 00:10:09,990 --> 00:10:11,880 We say current dot value is equal to 90. 258 00:10:11,880 --> 00:10:14,940 So we set the value of this node over here as 90. 259 00:10:15,060 --> 00:10:17,430 And then we call this dot remove. 260 00:10:17,430 --> 00:10:19,500 So we call the remove function again. 261 00:10:19,500 --> 00:10:22,920 But at this time we pass the value as 90. 262 00:10:22,920 --> 00:10:25,350 So the value at this point is 90 right. 263 00:10:25,350 --> 00:10:30,030 And then the current node is current dot right which is 90. 264 00:10:30,030 --> 00:10:31,830 So we pass the node 90. 265 00:10:31,830 --> 00:10:35,550 And then the parent over here the parent this is the third parameter is the parent right. 266 00:10:35,550 --> 00:10:39,870 So the parent at this point is the current node which is this node over here. 267 00:10:39,870 --> 00:10:42,450 Again it has the value 90 over here because it's same. 268 00:10:42,450 --> 00:10:44,280 But let's say you had 82 over here. 269 00:10:44,280 --> 00:10:45,990 Let's again just for understanding. 270 00:10:45,990 --> 00:10:48,780 Let's have this case where we have 82 over here. 271 00:10:50,140 --> 00:10:50,470 Right. 272 00:10:50,470 --> 00:10:56,170 So in this case, we would have, uh, put 82 over here and then the value would have been passed as 273 00:10:56,170 --> 00:11:01,420 82 and the current will be current dot right, which is 90. 274 00:11:01,420 --> 00:11:02,110 Right. 275 00:11:02,110 --> 00:11:04,480 And the parent will be this node. 276 00:11:04,480 --> 00:11:06,190 It would have had the value 82. 277 00:11:06,190 --> 00:11:06,400 Right. 278 00:11:06,400 --> 00:11:07,450 This one over here. 279 00:11:07,450 --> 00:11:07,780 All right. 280 00:11:07,780 --> 00:11:10,960 So we are passing the current which we are passing this node. 281 00:11:10,960 --> 00:11:14,110 We are passing this node and we are passing the value 90. 282 00:11:14,140 --> 00:11:18,190 Now what will happen over here is again we are coming inside the remove function. 283 00:11:18,190 --> 00:11:24,010 Now we, we have the uh the root the current is this dot. 284 00:11:24,010 --> 00:11:25,660 The current is what what is current. 285 00:11:25,660 --> 00:11:26,440 Let's just check that. 286 00:11:26,440 --> 00:11:27,070 That's 90. 287 00:11:27,070 --> 00:11:27,400 Right. 288 00:11:27,400 --> 00:11:28,900 So this is current itself. 289 00:11:29,660 --> 00:11:33,950 At this point we are taking the example where we don't have 82, so let's not get confused. 290 00:11:33,950 --> 00:11:38,390 So we are taking the case where we are trying to delete this 90, right. 291 00:11:38,390 --> 00:11:40,970 So we are checking whether current is truthy. 292 00:11:40,970 --> 00:11:41,540 Yes it is. 293 00:11:41,540 --> 00:11:44,840 And then we come inside and 90 is not less than 90. 294 00:11:44,840 --> 00:11:46,310 90 is not greater than 90. 295 00:11:46,310 --> 00:11:49,730 So we come to the else part and we see that we have found the node. 296 00:11:49,730 --> 00:11:52,820 So over here again we check whether there are two children. 297 00:11:52,820 --> 00:11:55,010 In this case 90 does not have two children. 298 00:11:55,010 --> 00:11:56,600 So it comes to the else part. 299 00:11:56,600 --> 00:11:57,920 Is the parent null. 300 00:11:57,920 --> 00:11:59,600 No the parent is this node over here. 301 00:11:59,600 --> 00:11:59,780 Right. 302 00:11:59,780 --> 00:12:00,560 This one over here. 303 00:12:00,560 --> 00:12:02,990 So it's we are not trying to remove the root node. 304 00:12:02,990 --> 00:12:06,740 And so we come out of this else part and then we come to this part. 305 00:12:06,740 --> 00:12:09,890 Else if current is equal to parent dot left. 306 00:12:09,890 --> 00:12:11,780 So that's not the case. 307 00:12:11,780 --> 00:12:12,770 This is a right child. 308 00:12:12,770 --> 00:12:14,540 So we say current is parent dot right. 309 00:12:14,540 --> 00:12:15,080 Which is true. 310 00:12:15,080 --> 00:12:15,950 This is the parent. 311 00:12:15,950 --> 00:12:17,240 This is the parent right. 312 00:12:17,240 --> 00:12:19,160 Let me just clear this up a little bit. 313 00:12:21,430 --> 00:12:21,730 All right. 314 00:12:21,730 --> 00:12:23,560 So we place the value 90 over here. 315 00:12:23,560 --> 00:12:24,460 This is the parent. 316 00:12:24,460 --> 00:12:26,470 So current is parent dot right. 317 00:12:26,470 --> 00:12:27,550 Yes that's the case. 318 00:12:27,550 --> 00:12:33,340 So we say parent dot right is equal to if this has a child then we would have taken that child. 319 00:12:33,340 --> 00:12:35,110 But it does not have a left or right child. 320 00:12:35,110 --> 00:12:36,460 So we are just checking that over here. 321 00:12:36,460 --> 00:12:36,850 Right. 322 00:12:36,850 --> 00:12:41,260 If it will definitely not have two children because it did not go over here. 323 00:12:41,260 --> 00:12:41,530 Right. 324 00:12:41,530 --> 00:12:45,310 If it had two children it would have gone over here right in this if loop. 325 00:12:45,310 --> 00:12:47,410 So we are sure that it does not have two children. 326 00:12:47,410 --> 00:12:48,670 So it has only one child. 327 00:12:48,670 --> 00:12:50,830 Now we are just checking the order does not matter. 328 00:12:50,830 --> 00:12:54,700 We are just checking if there is a left child then say parent dot right. 329 00:12:54,700 --> 00:12:55,690 Is that left child? 330 00:12:55,690 --> 00:12:59,140 If there is a right child, let's say parent dot right is the right child. 331 00:12:59,140 --> 00:12:59,860 So that's it. 332 00:12:59,860 --> 00:13:02,890 So it will definitely have only one child if at all it has a child. 333 00:13:02,890 --> 00:13:05,440 Now in this case we see that it does not have a child. 334 00:13:05,440 --> 00:13:06,970 So we set this to null right. 335 00:13:06,970 --> 00:13:07,480 So what. 336 00:13:07,480 --> 00:13:08,290 How is it working. 337 00:13:08,290 --> 00:13:09,760 We are checking if there is a left child. 338 00:13:09,760 --> 00:13:11,230 No, there is no left child. 339 00:13:11,230 --> 00:13:14,440 So we are setting parent dot right to its right. 340 00:13:14,440 --> 00:13:16,960 So the right of this node over here is null itself. 341 00:13:16,960 --> 00:13:19,660 So we are saying parent dot right is equal to null. 342 00:13:19,660 --> 00:13:22,210 And that's how we have deleted this 90. 343 00:13:22,210 --> 00:13:25,360 So at the end we will have 76 5043 over here. 344 00:13:25,360 --> 00:13:26,830 And over here we will have 90. 345 00:13:26,860 --> 00:13:28,390 There will be no right child. 346 00:13:28,390 --> 00:13:29,320 This will be just null. 347 00:13:29,320 --> 00:13:31,450 And the left child will be 78. 348 00:13:31,990 --> 00:13:32,440 All right. 349 00:13:32,440 --> 00:13:38,140 So we have taken care of the situation where we had to delete and we are deleting a node which has two 350 00:13:38,140 --> 00:13:38,650 children. 351 00:13:38,650 --> 00:13:41,140 So let me just make some space clear this up. 352 00:13:41,140 --> 00:13:47,590 Now what happens if we are trying to delete a child, a node which has only one child or zero children? 353 00:13:47,590 --> 00:13:51,700 So let's just take a look at those cases as well and run through the code. 354 00:13:52,030 --> 00:13:54,160 So for this let's take two examples. 355 00:13:54,160 --> 00:13:57,790 So over here we have 50 which has one child. 356 00:13:57,790 --> 00:14:01,810 And let's say we have 78 which has no child. 357 00:14:01,810 --> 00:14:03,190 So we are trying to delete these two. 358 00:14:03,190 --> 00:14:05,890 So let's get started with the case where we have 50. 359 00:14:05,890 --> 00:14:07,300 So we pass the value. 360 00:14:07,330 --> 00:14:08,380 We come over here. 361 00:14:08,380 --> 00:14:11,260 And again it's not an empty binary search tree. 362 00:14:11,260 --> 00:14:13,420 So we have the node 50. 363 00:14:13,420 --> 00:14:15,430 So we are starting with this the first case. 364 00:14:15,430 --> 00:14:18,550 So we are checking whether 50 is less than 76. 365 00:14:18,550 --> 00:14:19,510 Yes that's true. 366 00:14:19,510 --> 00:14:21,250 So we move in the left direction. 367 00:14:21,250 --> 00:14:24,160 So the parent is set to this and the current is over here. 368 00:14:24,160 --> 00:14:29,380 Now again we come to the while loop again and we have the current as 50. 369 00:14:29,410 --> 00:14:30,280 It's still truthy. 370 00:14:30,280 --> 00:14:32,470 So we are checking whether 50 is less than 50. 371 00:14:32,470 --> 00:14:33,070 No. 372 00:14:33,070 --> 00:14:34,480 Is 50 greater than 50. 373 00:14:34,480 --> 00:14:34,840 No. 374 00:14:34,840 --> 00:14:37,540 So that means we have found the node and we are over here. 375 00:14:37,960 --> 00:14:41,860 Now we are checking whether 50 has two children which is not the case. 376 00:14:41,860 --> 00:14:46,330 So we come over here is 50 is parent null or are we checking. 377 00:14:46,330 --> 00:14:49,030 We are checking whether 50 is the root node which is not the case. 378 00:14:49,030 --> 00:14:55,210 So then we come over here and we are checking whether 50 is a left child, whether 50 current is parent 379 00:14:55,210 --> 00:14:56,290 dot left which is true. 380 00:14:56,290 --> 00:15:01,150 So we come inside over here and we say parent dot left is its child. 381 00:15:01,150 --> 00:15:03,430 So we are just checking whether this has a child. 382 00:15:03,430 --> 00:15:05,260 It will definitely not have two children right. 383 00:15:05,260 --> 00:15:07,690 Because in that case it would have gone in over here. 384 00:15:07,690 --> 00:15:10,270 So it has only one child if at all it has a child. 385 00:15:10,270 --> 00:15:12,220 So we are checking does it have a left child. 386 00:15:12,220 --> 00:15:13,000 Yes it has. 387 00:15:13,000 --> 00:15:16,990 So we say parent dot left is the left child of 50 which is this. 388 00:15:16,990 --> 00:15:20,080 So we are removing this node and we are making this connection over here. 389 00:15:20,080 --> 00:15:21,970 So we have removed this node. 390 00:15:21,970 --> 00:15:22,420 All right. 391 00:15:22,420 --> 00:15:27,970 Now what happens if we are just trying to remove a node which has no children for example 78. 392 00:15:28,000 --> 00:15:29,350 Let's just clear this up. 393 00:15:31,630 --> 00:15:32,110 All right. 394 00:15:32,110 --> 00:15:36,280 So if you are trying to remove 78 again we start at the root right. 395 00:15:36,280 --> 00:15:37,180 We have 76. 396 00:15:37,180 --> 00:15:38,860 We we are comparing the values. 397 00:15:39,010 --> 00:15:40,930 Is 78 less than 76. 398 00:15:40,930 --> 00:15:41,440 No. 399 00:15:41,530 --> 00:15:43,360 Is 78 greater than 76. 400 00:15:43,360 --> 00:15:43,750 Yes. 401 00:15:43,750 --> 00:15:47,050 So we say parent is equal to current which is this one. 402 00:15:47,050 --> 00:15:48,490 So this will be the parent again. 403 00:15:48,490 --> 00:15:50,230 And current is current dot right. 404 00:15:50,230 --> 00:15:51,010 So current dot right. 405 00:15:51,010 --> 00:15:51,910 Is this one over here. 406 00:15:51,910 --> 00:15:54,850 So this is current which is 80 right now. 407 00:15:54,850 --> 00:15:57,940 Again uh we come back and it's still truthy. 408 00:15:57,970 --> 00:16:01,270 Now we are going to check whether 88 and 78. 409 00:16:01,270 --> 00:16:03,250 So 78 is the value right. 410 00:16:03,250 --> 00:16:06,310 We see that 78 which is the value is less than 80. 411 00:16:06,310 --> 00:16:07,690 So 78 is less than 80. 412 00:16:07,690 --> 00:16:09,640 So we move in this direction right. 413 00:16:09,640 --> 00:16:11,830 So we say current is current dot left. 414 00:16:11,830 --> 00:16:15,460 And again we come to the while loop and we check and current is truthy. 415 00:16:15,460 --> 00:16:17,050 So this is current at this point. 416 00:16:17,050 --> 00:16:18,820 And this is the parent at this point. 417 00:16:18,820 --> 00:16:24,370 Now we see that the value is 78 is not less than 78, 78 is not greater than 78. 418 00:16:24,370 --> 00:16:29,770 So we come over here to the else part and we have found the route which is to be the node, the node 419 00:16:29,770 --> 00:16:30,850 which is to be deleted. 420 00:16:30,850 --> 00:16:33,220 Now we are checking whether this node has two children. 421 00:16:33,220 --> 00:16:35,110 No it does not have two children. 422 00:16:35,110 --> 00:16:36,370 Is this node the root. 423 00:16:36,370 --> 00:16:37,270 No it's not. 424 00:16:37,270 --> 00:16:40,030 So we are just checking is this a left child or a right child. 425 00:16:40,030 --> 00:16:41,560 We see that it's a left child. 426 00:16:41,560 --> 00:16:46,450 So we come over here and we say parent dot left is any child if it has. 427 00:16:46,450 --> 00:16:48,220 So we are checking whether it has a left child. 428 00:16:48,220 --> 00:16:49,840 Does 78 have a left child. 429 00:16:49,840 --> 00:16:50,320 No. 430 00:16:50,320 --> 00:16:55,390 So in that case we are just assigning parent dot left as the current dot right. 431 00:16:55,390 --> 00:16:56,950 Current dot right over here is null. 432 00:16:56,950 --> 00:16:57,880 So this is null. 433 00:16:57,880 --> 00:17:00,610 So what we are doing is parent dot left is null. 434 00:17:00,610 --> 00:17:03,190 In that way we are removing this node. 435 00:17:03,190 --> 00:17:03,640 All right. 436 00:17:03,640 --> 00:17:05,590 So we have seen all the three cases. 437 00:17:05,590 --> 00:17:10,240 Now let's also see the case where we are trying to remove the root node. 438 00:17:10,240 --> 00:17:11,500 So what's happening over here. 439 00:17:11,500 --> 00:17:13,240 Let's just quickly see that as well. 440 00:17:13,750 --> 00:17:16,150 So let's say we are trying to remove 76. 441 00:17:16,150 --> 00:17:17,980 So we come over here. 442 00:17:18,810 --> 00:17:24,150 We will again go through all this part, and then we will have found the node because the value is equal. 443 00:17:24,150 --> 00:17:24,450 Right. 444 00:17:24,450 --> 00:17:26,820 So we come over here and it has two children. 445 00:17:26,820 --> 00:17:28,170 So it has two children. 446 00:17:28,170 --> 00:17:29,040 So what do we do. 447 00:17:29,070 --> 00:17:29,880 We. 448 00:17:30,500 --> 00:17:34,760 Find the minimum value of the right subtree over here. 449 00:17:34,790 --> 00:17:35,750 Get min value. 450 00:17:35,750 --> 00:17:37,100 So we'll get 78. 451 00:17:37,100 --> 00:17:39,470 And we will say current dot value is 78. 452 00:17:39,470 --> 00:17:40,880 So this will be 78. 453 00:17:40,880 --> 00:17:45,440 Then we will call the remove function on this subtree right. 454 00:17:45,830 --> 00:17:47,090 So we are going to pass. 455 00:17:48,260 --> 00:17:49,430 80 as the current node. 456 00:17:49,430 --> 00:17:50,240 This is the current node. 457 00:17:50,240 --> 00:17:53,390 This is the parent node and the value to be deleted is 78. 458 00:17:53,390 --> 00:17:58,010 Again, we will find that this is a node with only one child and this will be deleted. 459 00:17:58,010 --> 00:17:59,870 So that's how it works over here. 460 00:17:59,870 --> 00:18:04,100 Now let's also see the case where we have just the root node right. 461 00:18:04,100 --> 00:18:06,260 So let's just see that also as well. 462 00:18:06,950 --> 00:18:12,650 Let's say the binary tree was something like this 76 and let's say it had one child 50. 463 00:18:12,680 --> 00:18:14,300 So what do we do in this case? 464 00:18:14,300 --> 00:18:16,910 In this case, again we are trying to remove 76. 465 00:18:16,910 --> 00:18:18,440 So we will come over here. 466 00:18:18,440 --> 00:18:22,280 We will come, we will we won't come inside because it does not have two children. 467 00:18:22,280 --> 00:18:27,770 So we come over here and we see that yes, it's the root node or its parent is null at this point right. 468 00:18:27,770 --> 00:18:28,460 Parent is null. 469 00:18:28,460 --> 00:18:30,830 So we are trying to remove the root node itself. 470 00:18:30,830 --> 00:18:33,740 Now we are going to check whether current dot left is null. 471 00:18:33,740 --> 00:18:35,900 So current dot left is not null. 472 00:18:35,900 --> 00:18:38,240 So in this case yes we have something over here. 473 00:18:38,240 --> 00:18:39,080 So what do we do. 474 00:18:39,080 --> 00:18:44,630 We put this value 50 over here and it's left and right will be put over here left and right. 475 00:18:44,630 --> 00:18:45,890 In this case it's just null. 476 00:18:45,890 --> 00:18:49,790 So in this way we will have removed, uh this 76. 477 00:18:49,790 --> 00:18:52,730 And we'll just have one node and that will be the root node. 478 00:18:52,730 --> 00:18:54,110 And it has 50 as value. 479 00:18:54,110 --> 00:18:55,790 And it's left and right is null. 480 00:18:55,790 --> 00:18:58,130 Now let's say again we are removing 50. 481 00:18:58,130 --> 00:18:59,420 So this is the scenario. 482 00:18:59,420 --> 00:19:02,060 Now we just have one node in the binary search tree. 483 00:19:02,060 --> 00:19:04,670 And its left is null and its right is null. 484 00:19:04,670 --> 00:19:07,490 And let's say we are trying to remove the node with value 50. 485 00:19:07,490 --> 00:19:12,410 So what happens again we will check the value and we will see that it's equal. 486 00:19:12,410 --> 00:19:13,700 So we will come over here. 487 00:19:13,700 --> 00:19:15,890 Now we see that it does not have two children. 488 00:19:15,890 --> 00:19:19,310 So we come over here we see that its parent is actually null. 489 00:19:19,310 --> 00:19:24,770 So we come over here and we see that it does not have a left child and it does not have a right child. 490 00:19:24,770 --> 00:19:29,630 So we come over here so we understand that we just need to remove a single node. 491 00:19:29,630 --> 00:19:33,320 And the binary search tree has only a single node and it's the root itself. 492 00:19:33,320 --> 00:19:36,470 So in this case we just say that the root is equal to null. 493 00:19:36,470 --> 00:19:42,530 So in this case the we are just deleting the binary search tree and its root itself is null. 494 00:19:42,530 --> 00:19:44,630 So that's how the remove function works. 495 00:19:44,630 --> 00:19:45,080 All right. 496 00:19:45,080 --> 00:19:48,200 So let's quickly take a look at the complexity analysis. 497 00:19:48,200 --> 00:19:53,120 So the time complexity of this solution will be O of log n average. 498 00:19:53,120 --> 00:19:59,090 And best case because if the tree is balanced that is the height of log n is the height of the balanced 499 00:19:59,090 --> 00:19:59,300 tree. 500 00:19:59,300 --> 00:19:59,660 Right. 501 00:19:59,660 --> 00:20:03,410 And it will be O of n if it's an unbalanced binary search tree. 502 00:20:03,410 --> 00:20:04,160 Something like this. 503 00:20:04,190 --> 00:20:09,080 We have already discussed that right now the space complexity you can see is equal to O of one. 504 00:20:09,080 --> 00:20:12,560 We are making only one recursive call right over here. 505 00:20:12,560 --> 00:20:12,920 Right. 506 00:20:12,920 --> 00:20:15,830 So you can say that the space complexity is O of two. 507 00:20:15,830 --> 00:20:17,420 But then this is just a constant. 508 00:20:17,420 --> 00:20:21,110 So we get that the space complexity is equal to O of one. 509 00:20:21,110 --> 00:20:27,230 So this is the iterative solution where we where we implement the function remove to remove a node from 510 00:20:27,230 --> 00:20:28,250 the binary search tree.