1 00:00:01,440 --> 00:00:02,100 Hi, everyone. 2 00:00:02,130 --> 00:00:06,240 So today we are going to solve this question, check if a binary tree. 3 00:00:07,290 --> 00:00:08,550 Is a birthday or not? 4 00:00:09,330 --> 00:00:14,680 OK, so first of all, what is so BSU stands for by history? 5 00:00:14,970 --> 00:00:19,190 OK, and what is the property of a beast so invested? 6 00:00:19,190 --> 00:00:21,620 The properties of Vesti are very simple. 7 00:00:21,930 --> 00:00:24,060 So suppose you have this root node. 8 00:00:25,490 --> 00:00:35,090 OK, so if will go left, then all the nodes in the left hand side, so their data will be less than 9 00:00:35,120 --> 00:00:36,440 the data of the root node. 10 00:00:39,410 --> 00:00:43,370 Similarly, if you will go in the right hand side of the root node, then. 11 00:00:44,490 --> 00:00:46,050 The data of all the nodes. 12 00:00:47,100 --> 00:00:49,320 Will be greater than the data through a.. 13 00:00:49,770 --> 00:00:52,680 OK, so this is very simple property of obesity. 14 00:00:53,360 --> 00:00:53,760 OK. 15 00:00:53,940 --> 00:00:56,030 And so what is the input? 16 00:00:56,060 --> 00:01:02,160 So the input given is basically a binary tree and we have to return a boolean value. 17 00:01:02,670 --> 00:01:07,200 OK, whether that by the tree, if the banditry is about, I will return. 18 00:01:07,200 --> 00:01:10,770 True, if the binary trees not vestey then I will return false. 19 00:01:11,520 --> 00:01:13,920 OK, so how can I solve this question. 20 00:01:14,990 --> 00:01:17,280 So there are two ways to solve this question. 21 00:01:17,500 --> 00:01:19,140 OK, so the first we. 22 00:01:20,760 --> 00:01:27,000 So the first race, basically, we know that in order traversal of a BSD sorted, OK, this is the property 23 00:01:27,000 --> 00:01:31,920 for Besty, the in order traversal of best is sorted. 24 00:01:32,400 --> 00:01:33,330 So very simple. 25 00:01:33,850 --> 00:01:36,260 OK, so consider this example. 26 00:01:36,300 --> 00:01:37,340 This is a binary tree. 27 00:01:37,590 --> 00:01:39,150 So what is in order traversal? 28 00:01:39,150 --> 00:01:46,080 So in order to resources, first you visit the left subtree, then the current node data and then the 29 00:01:46,080 --> 00:01:46,930 right subtree. 30 00:01:46,980 --> 00:01:54,270 OK, so Ali, are now let us consider this binary tree and now let us perform it's traversal. 31 00:01:55,260 --> 00:01:56,870 So what will be the traversal. 32 00:01:56,880 --> 00:01:58,110 So suppose this is the. 33 00:01:58,150 --> 00:01:59,250 So this is the root node. 34 00:02:00,950 --> 00:02:06,160 So terror cell will be one, then two, then three, then four and then five. 35 00:02:06,220 --> 00:02:09,860 OK, now you can check this is basically sorted. 36 00:02:11,039 --> 00:02:12,070 One, two, three, four, five. 37 00:02:12,090 --> 00:02:18,600 This is sorted so I can see that this binary tree is basically Vesti. 38 00:02:18,670 --> 00:02:27,740 OK, so this binary tree is besty because it's traversal is sorted and only BSD there was in reversal 39 00:02:27,750 --> 00:02:28,210 sorted. 40 00:02:28,620 --> 00:02:31,860 Now let us perform the reversal of this bindery. 41 00:02:32,080 --> 00:02:37,770 OK, so it will be one, then five, then three, then four and then six. 42 00:02:37,990 --> 00:02:42,100 OK, so basically this is not sorted since this is not sorted. 43 00:02:42,270 --> 00:02:44,860 So this by military is not besty. 44 00:02:44,910 --> 00:02:46,920 OK, so this is not Vesty. 45 00:02:47,820 --> 00:02:50,050 You can see season or number four. 46 00:02:50,190 --> 00:02:56,640 OK, so this normal four qualifies for bisdee, but this note number five does not qualify because in 47 00:02:56,640 --> 00:02:59,280 the left hand side you have one perfectly fine. 48 00:02:59,490 --> 00:03:05,140 But in the right hand side you have this node four and four is basically less than five. 49 00:03:05,340 --> 00:03:07,860 So this binary is not Vesti. 50 00:03:09,030 --> 00:03:15,710 OK, so the first way to solve this question, what we will do, so we will perform the travesty of 51 00:03:15,720 --> 00:03:18,930 the best and let's say we will store the result in energy. 52 00:03:19,800 --> 00:03:27,500 OK, so what we will do, we will restore the traversal of the given by Nutri in an area. 53 00:03:28,080 --> 00:03:32,640 So this area will contain the reversal of the binary tree of the given by Nutri. 54 00:03:32,790 --> 00:03:36,150 Then I will check whether this area is sorted area or not. 55 00:03:36,960 --> 00:03:41,840 If this is sorted, then I will return to the given by is best. 56 00:03:42,240 --> 00:03:45,360 If this area is not sorted, then I will return false. 57 00:03:45,390 --> 00:03:49,290 So this binary is not the best if that is not sorted. 58 00:03:49,810 --> 00:03:51,490 OK, so very simple approach. 59 00:03:51,780 --> 00:03:54,750 So what would be the time and the space complexity of this approach? 60 00:03:55,000 --> 00:03:58,500 So time complexity is basically so we have to go through each and every node. 61 00:03:58,740 --> 00:04:04,860 So suppose there are end nodes so time complexity will be big off and and what is the space complexity. 62 00:04:04,890 --> 00:04:08,640 So it will be big off and OK, we have to store and node. 63 00:04:10,920 --> 00:04:15,060 So what is and is basically the total number of nodes present in the binary tree? 64 00:04:15,480 --> 00:04:19,290 OK, so this is the time in this space complexity of using this approach. 65 00:04:20,360 --> 00:04:27,200 Now, one thing that I want to share is basically so what we can do here is so there's no need to create 66 00:04:27,470 --> 00:04:27,730 this. 67 00:04:28,230 --> 00:04:30,150 OK, there is no need to create this idea. 68 00:04:30,170 --> 00:04:35,620 So what we will do so we will take two pointer, previous pointer and the current pointer. 69 00:04:35,900 --> 00:04:38,240 And while we are doing the traversal. 70 00:04:39,680 --> 00:04:47,540 While we are performing the traversal we will check, previous data should be less than the data current 71 00:04:47,540 --> 00:04:47,930 data. 72 00:04:47,990 --> 00:04:55,280 OK, so if this condition is always valid, then basically the error is sorted, then sorted so you 73 00:04:55,280 --> 00:04:57,570 can return bisdee the given by degrees. 74 00:04:58,340 --> 00:05:07,250 And if at any point this condition fails, basically previous data is greater than current data, then 75 00:05:07,250 --> 00:05:08,540 you can return that. 76 00:05:08,540 --> 00:05:13,320 The given by Nutri is not about because it's in at least not sorted. 77 00:05:13,700 --> 00:05:18,230 OK, so here, how do we check whether it is sorted or not? 78 00:05:18,260 --> 00:05:25,460 Basically we take two pointers, so previous and current pointer and we will check that previous data 79 00:05:25,460 --> 00:05:28,260 should be less than the date of the current pointer. 80 00:05:28,280 --> 00:05:29,870 OK, so this weekend can. 81 00:05:30,690 --> 00:05:36,530 So instead of creating this area when we are performing the traversal, we can check this condition 82 00:05:36,530 --> 00:05:37,380 for every node. 83 00:05:37,820 --> 00:05:44,360 OK, so in this way the time complexity is still big often, but the space complexity will be Goffman 84 00:05:44,600 --> 00:05:46,190 because there is no need to create. 85 00:05:47,500 --> 00:05:48,100 This Eddie. 86 00:05:48,130 --> 00:05:49,900 OK, there's no need to create this, Eddie. 87 00:05:50,770 --> 00:05:53,850 Now, let's discuss the second way of solving this question, OK? 88 00:05:55,330 --> 00:06:03,760 So let us take this example, four to five, one three, so I have this for two, then five and I have 89 00:06:03,760 --> 00:06:05,290 one and then I have three. 90 00:06:05,350 --> 00:06:08,990 OK, so let's discuss the second way of solving this question. 91 00:06:10,480 --> 00:06:15,850 So what we're going to do here is so basically each node has some constraint. 92 00:06:15,920 --> 00:06:19,730 OK, so each node has some constraint and what is that constraint? 93 00:06:20,500 --> 00:06:22,990 So let's discuss that constraint for the root node. 94 00:06:23,680 --> 00:06:29,110 So this value, this value can be from minus infinity to plus infinity. 95 00:06:29,120 --> 00:06:31,210 It can be anything, OK? 96 00:06:31,390 --> 00:06:35,500 Root data can be anything but if it will go in the left hand side. 97 00:06:37,010 --> 00:06:43,970 Suppose the input is basically about, OK, so suppose I am discussing the property of about OK, I 98 00:06:44,000 --> 00:06:45,260 am discussing the property, everybody. 99 00:06:45,650 --> 00:06:47,510 So if it will go in the left hand side. 100 00:06:48,810 --> 00:06:52,530 What can be the data of this value, what can be the data for this? 101 00:06:52,530 --> 00:06:53,430 Not so. 102 00:06:53,430 --> 00:07:00,600 The minimum value can be minus infinity, but the maximum value can be four by four, because four is 103 00:07:00,600 --> 00:07:01,320 the root node. 104 00:07:02,300 --> 00:07:08,450 OK, so the value of this node will lie between minus infinity to four, because this is the property 105 00:07:08,450 --> 00:07:11,090 of the best that if it will go in the left hand side. 106 00:07:12,500 --> 00:07:18,080 So the left the debate of the left node will always be smaller than the route node data. 107 00:07:19,070 --> 00:07:23,720 OK, so for this node, this is the constraint. 108 00:07:24,230 --> 00:07:27,200 The value will lie between minus infinity for OK. 109 00:07:27,410 --> 00:07:29,270 Now suppose you again go left. 110 00:07:30,420 --> 00:07:31,680 So for Naude, No. 111 00:07:31,740 --> 00:07:32,140 One. 112 00:07:32,160 --> 00:07:37,860 So basically for disaccord, the minimum value will be minus infinity, but the maximum value can be 113 00:07:37,860 --> 00:07:38,490 two only. 114 00:07:38,710 --> 00:07:43,170 OK, the maximum value will be two if you will go in the right hand side. 115 00:07:44,300 --> 00:07:48,080 So the minimum value will be to and the maximum value will be for. 116 00:07:48,260 --> 00:07:51,570 OK, so this for the maximum value will be for. 117 00:07:51,950 --> 00:07:54,350 So the only possible in this three. 118 00:07:55,410 --> 00:07:57,120 Now, if you were going the right hand side. 119 00:07:58,250 --> 00:08:02,690 So basically, it's minimum wage level before and it's maximum value will be infinity. 120 00:08:03,930 --> 00:08:04,950 OK, so. 121 00:08:06,120 --> 00:08:15,510 Each node has constrained OK, each node data, each node data is bounded by a constraint that its maximum 122 00:08:15,510 --> 00:08:19,590 value will be, it will lie between the minimum and the maximum value. 123 00:08:19,590 --> 00:08:23,340 Each data will lie between a certain minimum and the maximum value. 124 00:08:24,210 --> 00:08:26,280 OK, let us take one more example. 125 00:08:26,280 --> 00:08:33,370 So suppose I have five then let's say I have this X and here I have Y. 126 00:08:33,419 --> 00:08:38,789 OK, so here I have Z and let's say here I have and here I have B. 127 00:08:39,010 --> 00:08:40,320 OK, so. 128 00:08:41,419 --> 00:08:44,700 This value can be from minus invader infinity. 129 00:08:45,410 --> 00:08:51,860 OK, so its value, so the value will be minus infinity and the maximum value will be five. 130 00:08:52,810 --> 00:08:57,550 If you will go again in the left hand side, the minimum values still minus infinity, but the maximum 131 00:08:57,550 --> 00:08:58,350 value is X. 132 00:08:59,020 --> 00:09:00,430 OK, now for Y. 133 00:09:01,360 --> 00:09:02,660 So what can be the values of. 134 00:09:02,890 --> 00:09:07,390 So basically the minimum value will be five and the maximum value will be infinity. 135 00:09:08,550 --> 00:09:14,450 For this note, the minimum, if you are going in the left hand side, so basically the minimum value 136 00:09:14,490 --> 00:09:15,730 will be five. 137 00:09:15,780 --> 00:09:23,040 OK, so this five, the minimum value will be five and the maximum value will be by OK, if you are 138 00:09:23,040 --> 00:09:24,330 going in the right hand side. 139 00:09:24,600 --> 00:09:28,410 So the minimum value will be way and the maximum value will be infinity. 140 00:09:29,250 --> 00:09:31,180 OK, so what is the second approach. 141 00:09:31,560 --> 00:09:33,450 So second approach says. 142 00:09:34,630 --> 00:09:38,860 Basically, you check the constraint of every node. 143 00:09:39,520 --> 00:09:45,340 OK, I will check the constraint for every node if the constraint is valid, if all the nodes. 144 00:09:46,550 --> 00:09:49,740 Are having this constraint then it is about race. 145 00:09:49,760 --> 00:09:50,870 It is not about. 146 00:09:52,050 --> 00:10:00,470 OK, I'm repeating myself, the second approach will go to each and every node, OK, approaches, go 147 00:10:00,480 --> 00:10:03,570 to each node and check their constraint. 148 00:10:03,600 --> 00:10:05,110 OK, what is the constraint? 149 00:10:05,370 --> 00:10:07,560 So this is the constraint of data constraint. 150 00:10:07,740 --> 00:10:11,630 If every node follows the data constraint, OK, it is very simple. 151 00:10:12,000 --> 00:10:16,410 If every node follows its data constraint, then it is a BSD. 152 00:10:16,440 --> 00:10:20,180 Otherwise it is not OK if every in order for the constraint. 153 00:10:20,970 --> 00:10:25,500 So if it is true then the given binit it is best raise. 154 00:10:25,620 --> 00:10:28,200 The given by Nutri is not ok. 155 00:10:30,920 --> 00:10:34,430 So I think this approach, number one, is very easy to implement. 156 00:10:34,610 --> 00:10:42,260 OK, so what we are doing, we will just perform the traversal and we will take two point up us point 157 00:10:42,260 --> 00:10:43,000 and point out. 158 00:10:43,010 --> 00:10:45,030 And we will we will have to check this condition. 159 00:10:45,050 --> 00:10:47,810 OK, then we can return whether the. 160 00:10:48,780 --> 00:10:53,470 Guarantees BSG or not, but the second approach, I think, is a little bit difficult. 161 00:10:53,790 --> 00:10:55,860 So let us implement the second approach. 162 00:10:56,740 --> 00:11:02,270 OK, so what we will do is first let us take this example. 163 00:11:02,280 --> 00:11:03,840 Also five 146. 164 00:11:04,530 --> 00:11:08,290 OK, now let us check whether this five 146. 165 00:11:09,150 --> 00:11:14,040 So I have five one four and then I have three and six. 166 00:11:15,060 --> 00:11:20,080 OK, so its value can be from minus infinity to infinity and its value is five. 167 00:11:20,100 --> 00:11:21,270 So this note is correct. 168 00:11:22,340 --> 00:11:30,290 If I'm going on the left hand side, so its value will be from minus infinity to five and one lies between 169 00:11:30,290 --> 00:11:30,590 this. 170 00:11:30,740 --> 00:11:32,640 OK, so this node is also correct. 171 00:11:32,950 --> 00:11:34,640 Now check this node for. 172 00:11:35,550 --> 00:11:42,480 So it's minimum value is basically five and it's maximum value is basically infinity, and four does 173 00:11:42,480 --> 00:11:44,370 not lie between five and infinity. 174 00:11:44,820 --> 00:11:48,490 OK, so that means this tree is not a beast. 175 00:11:49,080 --> 00:11:54,030 OK, this tree is not beast because fall does not lie between five and infinity. 176 00:11:55,580 --> 00:11:57,420 OK, so what will be our approach? 177 00:11:58,070 --> 00:12:02,330 So we will take the help of regulation, we are implementing second approach. 178 00:12:03,080 --> 00:12:05,540 OK, so we will take the help of regulation. 179 00:12:05,550 --> 00:12:07,250 So this is the left subtree. 180 00:12:07,910 --> 00:12:09,770 This is the right subtree. 181 00:12:11,990 --> 00:12:17,570 OK, so what we will do, so I will call the functionality of the neural function is is bisdee. 182 00:12:18,880 --> 00:12:24,580 So I will call the function on the left hand side, the left hand side should be left subtree should 183 00:12:24,580 --> 00:12:25,150 be bisdee. 184 00:12:26,370 --> 00:12:26,750 Right. 185 00:12:26,770 --> 00:12:29,580 Somebody should be best and for. 186 00:12:30,120 --> 00:12:34,360 I will check whether the days lag between minus infinity to infinity. 187 00:12:34,890 --> 00:12:35,580 Very simple. 188 00:12:35,820 --> 00:12:42,900 OK, so your condition if the left to is a body, if the right is a beast, and if the narrator lies 189 00:12:42,900 --> 00:12:49,620 between minus infinity to infinity, then I will return to that the given prize bastia that I will return 190 00:12:49,620 --> 00:12:50,010 false. 191 00:12:50,220 --> 00:12:52,210 OK, so I hope you understand the logic. 192 00:12:52,230 --> 00:12:54,030 Now let us write the code, ok. 193 00:12:55,520 --> 00:12:59,990 So basically, this is a legitimate question validated by necessity. 194 00:13:00,050 --> 00:13:03,070 OK, so now let us write the code. 195 00:13:03,230 --> 00:13:04,490 OK, so one thing. 196 00:13:05,330 --> 00:13:11,600 So I told you that the value of fruit will basically lie between minus infinity and basically plus infinity. 197 00:13:11,810 --> 00:13:14,550 So let us define what R minus and plus infinity. 198 00:13:14,570 --> 00:13:18,770 OK, what what is the meaning of minus infinity and what is the meaning of plus infinity. 199 00:13:19,220 --> 00:13:24,650 OK, so basically in C++ integer itself, 32 bits. 200 00:13:26,580 --> 00:13:33,350 OK, so that means the maximum value of integer can be to the power 31 and the minimum value of integer 201 00:13:33,350 --> 00:13:36,050 can be minus two to the power to be one minus one. 202 00:13:36,110 --> 00:13:41,360 OK, so this is basically let's call it it is nearly equal to the power nine. 203 00:13:41,570 --> 00:13:45,950 And similarly this is also nearly equal to minus 10 to the power nine. 204 00:13:46,190 --> 00:13:49,080 OK, so by plus infinity. 205 00:13:49,130 --> 00:13:51,460 OK, so this plus infinity. 206 00:13:51,800 --> 00:13:52,830 So it should be good. 207 00:13:52,850 --> 00:13:58,660 Then at about nine let's call it ten to the power 10 and similarly this minus infinity. 208 00:13:58,940 --> 00:14:03,490 So this should be listin ten to the power minus the power line. 209 00:14:03,740 --> 00:14:06,380 So let's call it minus 20 the power then. 210 00:14:07,220 --> 00:14:08,990 OK, so these are distributed. 211 00:14:10,090 --> 00:14:11,350 So they are inclusive. 212 00:14:11,380 --> 00:14:18,430 OK, so for root, root can take the valley of basically minus 10 to the power line and it can take 213 00:14:18,430 --> 00:14:20,500 the valley of the power line. 214 00:14:20,560 --> 00:14:22,960 OK, so now let's ride the gold. 215 00:14:24,670 --> 00:14:26,630 So this is basically a little problem. 216 00:14:26,650 --> 00:14:31,690 OK, so their function is bull and then it's basically a root. 217 00:14:31,880 --> 00:14:39,160 OK, so let us create a helper function so that the helper function will be able. 218 00:14:40,640 --> 00:14:42,230 So what this function will take? 219 00:14:43,240 --> 00:14:44,530 This function will take. 220 00:14:45,870 --> 00:14:46,560 Root node. 221 00:14:47,920 --> 00:14:50,260 And the minimum and the maximum value of the loot. 222 00:14:50,650 --> 00:14:54,700 OK, so here the what is the minimum? 223 00:14:54,700 --> 00:14:55,230 The maximum. 224 00:14:56,050 --> 00:15:01,760 So the normal life between minus infinity to plus infinity and both are inclusive. 225 00:15:01,780 --> 00:15:09,220 OK, so minus infinity is basically minus 10 to the power nine and plus introduced into the lower nine. 226 00:15:09,260 --> 00:15:11,910 OK, so what I will pass. 227 00:15:11,920 --> 00:15:13,000 So I am passing. 228 00:15:13,780 --> 00:15:14,880 These are inclusive. 229 00:15:15,130 --> 00:15:22,060 So that means if I want to exclude this I can write minus 10 to the power, Ten Commandments, the power 230 00:15:22,060 --> 00:15:22,350 then. 231 00:15:22,750 --> 00:15:25,870 But this number is big so it cannot be stored in integer. 232 00:15:25,870 --> 00:15:27,220 So I will store it long. 233 00:15:27,220 --> 00:15:27,550 Long. 234 00:15:28,450 --> 00:15:33,880 OK, this number is big, so I cannot turn it in, so who have to store this number in a long, long 235 00:15:33,880 --> 00:15:34,930 and similarly for this? 236 00:15:35,180 --> 00:15:37,060 OK, so I have to take long, long. 237 00:15:38,860 --> 00:15:45,820 So this route will lie between two variables, minimum and the maximum, so the minimum value is basically 238 00:15:46,030 --> 00:15:51,420 you can pass the default argument, so then minimum will be minus 10 to the power 10. 239 00:15:51,430 --> 00:15:56,110 OK, so 10 zeroes, one, two, three, four, five, six, seven, eight, nine, 10. 240 00:15:56,660 --> 00:15:57,100 OK. 241 00:15:58,330 --> 00:15:59,200 And similarly. 242 00:16:00,460 --> 00:16:06,480 The maximum value of fruit can be what is the maximum value of fruit, so it can be 10 to the Barberton. 243 00:16:06,530 --> 00:16:12,100 OK, it will be tendered about so one, two, three, four, five, six, seven, eight, nine, 10. 244 00:16:12,130 --> 00:16:13,190 And the rules, basically. 245 00:16:13,780 --> 00:16:14,590 So one thing. 246 00:16:16,270 --> 00:16:17,740 So here I am digging. 247 00:16:18,920 --> 00:16:24,240 Down to the bottom, you can also take 10 to the power, 11 or 10 to the power to end and so on, but 248 00:16:24,460 --> 00:16:26,910 the power then is will do our work. 249 00:16:26,930 --> 00:16:28,970 OK, so this is more than enough. 250 00:16:28,970 --> 00:16:29,910 It will do our job. 251 00:16:29,970 --> 00:16:33,800 And similarly, ministered to the power then will do our work. 252 00:16:33,860 --> 00:16:37,330 OK, so now what we have to do. 253 00:16:37,340 --> 00:16:38,620 So let us ride the bike. 254 00:16:38,840 --> 00:16:39,940 So what is the best case. 255 00:16:40,760 --> 00:16:47,460 So if through dismal IFPRI does not exist, then I can say that given by Nutri is basically biased. 256 00:16:47,510 --> 00:16:54,410 So I will return to OK now if we have to do first, let us check whether the left is biased or not. 257 00:16:54,650 --> 00:17:00,710 So let us call the helper function so I will pass the left subtree. 258 00:17:01,190 --> 00:17:02,480 So rude and left. 259 00:17:03,450 --> 00:17:09,569 Now, what is the minimum value, what is the minimum value for the left subtree, so it will be same 260 00:17:09,569 --> 00:17:11,130 as minimum value for the root. 261 00:17:12,349 --> 00:17:13,880 And what is the maximum value? 262 00:17:14,940 --> 00:17:19,050 So basically, the maximum value will be route data. 263 00:17:19,079 --> 00:17:21,540 OK, so Rotaru value. 264 00:17:24,150 --> 00:17:25,170 OK, so one thing. 265 00:17:26,550 --> 00:17:28,410 So if you have a binary tree. 266 00:17:29,940 --> 00:17:37,050 This is one, and this is one, so basically this Binit is not bisdee, OK, this is not Vesti because 267 00:17:37,920 --> 00:17:43,900 its range is between minus and to infinity, but its range is between minus infinity to one. 268 00:17:43,950 --> 00:17:47,760 OK, so basically this one is this one, OK? 269 00:17:47,940 --> 00:17:49,330 And this one is basically. 270 00:17:49,350 --> 00:17:53,960 So this is this type of this type of record means this one is not included. 271 00:17:54,000 --> 00:17:56,230 OK, this is not included. 272 00:17:56,250 --> 00:17:57,450 So this is excluded. 273 00:18:00,700 --> 00:18:07,200 So since this one equals close to this one, so that means this is not about OK, this is not about 274 00:18:07,300 --> 00:18:13,820 because strictly left values should be less than root values. 275 00:18:15,520 --> 00:18:18,620 OK, this is not less than articles two. 276 00:18:18,650 --> 00:18:20,350 This is strictly Leston, OK? 277 00:18:21,380 --> 00:18:26,840 So that's why if the input is this now put this this is not about OK. 278 00:18:28,710 --> 00:18:32,830 And similarly, let us check whether the right surprise you or not. 279 00:18:33,510 --> 00:18:35,250 So let us call the helper function. 280 00:18:36,640 --> 00:18:38,860 I will bust the right subtree. 281 00:18:40,860 --> 00:18:43,370 Now, what is the minimum wage, so minimum values? 282 00:18:43,410 --> 00:18:43,870 Nothing. 283 00:18:43,920 --> 00:18:44,400 It is. 284 00:18:45,780 --> 00:18:46,500 Rude value. 285 00:18:46,530 --> 00:18:46,860 OK. 286 00:18:47,890 --> 00:18:52,930 And what is the maximum value, so the maximum value is plus infinity, basically this number 10 to 287 00:18:52,930 --> 00:18:53,260 the power. 288 00:18:53,630 --> 00:18:53,980 OK. 289 00:18:55,140 --> 00:18:59,280 Now, our trees vista if and only if left some trees. 290 00:18:59,730 --> 00:19:07,710 So if left and right surprised Besty and the value of fruit. 291 00:19:10,860 --> 00:19:12,540 And the root value. 292 00:19:14,140 --> 00:19:18,400 Basically, it lies between plus infinity and minus infinity. 293 00:19:18,430 --> 00:19:19,540 OK, so this condition. 294 00:19:22,910 --> 00:19:25,310 So the value of fruit. 295 00:19:27,210 --> 00:19:30,420 So it should be basically greater than the minimum value. 296 00:19:31,410 --> 00:19:32,670 And it should be. 297 00:19:35,530 --> 00:19:40,720 Less than the maximum value, if these four conditions are true, then I will return to. 298 00:19:42,370 --> 00:19:44,470 In the elford, I will return false. 299 00:19:46,420 --> 00:19:53,830 OK, so let's call the helper function from Dimin, so return helper, when I will pass, I will pass 300 00:19:53,830 --> 00:19:54,360 on the road. 301 00:19:54,430 --> 00:19:56,590 OK, so these are default arguments. 302 00:19:57,800 --> 00:20:01,550 So let us not our call, and then we will try to submit our code, OK? 303 00:20:05,330 --> 00:20:07,220 OK, so now let's meet our good. 304 00:20:09,930 --> 00:20:11,800 OK, so our court is working fine. 305 00:20:11,820 --> 00:20:14,280 OK, now let's see what we are doing here. 306 00:20:16,460 --> 00:20:19,140 OK, so this helper function is doing all the work. 307 00:20:19,160 --> 00:20:21,350 OK, so this is taking root. 308 00:20:21,650 --> 00:20:26,720 So this is taking the minimum value of the root, which is which I'm calling minus infinity. 309 00:20:26,720 --> 00:20:32,600 And it is calling the plus it is calling the maximal of the root, which which I'm calling is plus infinity. 310 00:20:32,630 --> 00:20:35,150 OK, so four root node. 311 00:20:36,540 --> 00:20:41,340 The value is between minus infinity open bracket and plus infinity open bracket. 312 00:20:41,380 --> 00:20:47,460 OK, so the value of fruit can be close to two to the power to divine, which is the maximum value for 313 00:20:47,460 --> 00:20:48,120 an integer. 314 00:20:48,180 --> 00:20:52,160 OK, so and this value is equal to around 10 to the power nine. 315 00:20:52,410 --> 00:20:56,320 So to the power nine is basically included in this. 316 00:20:56,340 --> 00:21:02,730 OK, so that is about nine will be included from minus 10 to the power 10 to 10 to the power then. 317 00:21:02,820 --> 00:21:05,490 OK, so no problem then. 318 00:21:05,490 --> 00:21:08,220 If the root is nil, obviously we can directly return. 319 00:21:08,220 --> 00:21:10,440 True, because the given binary will be bisdee. 320 00:21:11,130 --> 00:21:15,990 Now I'm calling on the left subtree, then I am calling on the right subtree and then I am checking 321 00:21:15,990 --> 00:21:16,590 the condition. 322 00:21:16,870 --> 00:21:20,330 So if the left is the right, surprise Vesti. 323 00:21:20,520 --> 00:21:23,700 And now here I am checking the constraint on the root node. 324 00:21:23,880 --> 00:21:29,460 OK, so if the value of root node is greater than the minimum value and the value of node is less than 325 00:21:29,460 --> 00:21:33,270 the maximum value, then return to azn false. 326 00:21:33,330 --> 00:21:34,660 OK, so very simple. 327 00:21:34,860 --> 00:21:36,780 What is the time complexity of this approach? 328 00:21:37,050 --> 00:21:39,310 So basically we are going through each and every node. 329 00:21:39,330 --> 00:21:44,850 So if data and NATO time complexity is big off and now what does this space complexity. 330 00:21:45,510 --> 00:21:50,670 So the space complexity you can say or Draffin if you are considering the cost. 331 00:21:50,830 --> 00:21:52,410 So basically we are using recursion. 332 00:21:52,410 --> 00:21:54,570 So the recursion we have a call stack. 333 00:21:54,930 --> 00:22:00,900 So if you will consider this memory, if you will consider the constant memory, then it is ultrafine. 334 00:22:01,050 --> 00:22:02,790 Otherwise it is order of one. 335 00:22:03,730 --> 00:22:04,150 OK. 336 00:22:05,210 --> 00:22:10,400 Now, if you didn't like this approach, we also discussed about the first approach, what we can do. 337 00:22:10,670 --> 00:22:18,320 We will simply do traversal need traversal and we will store the sell output in an eddy. 338 00:22:19,630 --> 00:22:26,740 And if this stays sorted, then the then basically the binary trees, BSG either remains or does not. 339 00:22:27,190 --> 00:22:29,190 OK, so this is very simple to implement. 340 00:22:29,200 --> 00:22:30,610 It is very easy to implement. 341 00:22:30,850 --> 00:22:32,200 It can implement it yourself. 342 00:22:32,230 --> 00:22:37,840 OK, so in this case, also the time complexity we have already discussed Magoffin and the space complexity 343 00:22:37,840 --> 00:22:38,440 is also big. 344 00:22:38,440 --> 00:22:40,300 Often if you are creating the very. 345 00:22:41,450 --> 00:22:45,340 But if you will write code in a good matter, then there is no need to create this area. 346 00:22:45,500 --> 00:22:51,260 You can take two pointer, three pointer and current pointer and you can easily compare the date of 347 00:22:51,260 --> 00:22:57,340 these two points and you will be able to solve this problem in open space using the Internet. 348 00:22:57,860 --> 00:22:58,190 OK. 349 00:23:00,300 --> 00:23:02,790 So if you have any doubt in this question, you can ask me. 350 00:23:02,820 --> 00:23:03,600 OK, thank you.