1 00:00:01,620 --> 00:00:02,370 Hi, everyone. 2 00:00:02,400 --> 00:00:07,300 So in this very day, we will start writing the code for dysfunction, so we are taking in order to 3 00:00:07,620 --> 00:00:14,730 as important as input, but we discussed in our previous video that I need to create a function like 4 00:00:14,730 --> 00:00:15,030 this. 5 00:00:15,360 --> 00:00:24,020 I will create a function and I will pass in order to start, in order to start and end. 6 00:00:24,330 --> 00:00:27,510 So let's create this function and we will name it helper function. 7 00:00:29,130 --> 00:00:29,580 So what? 8 00:00:29,580 --> 00:00:30,870 This helper function will return. 9 00:00:31,900 --> 00:00:38,890 So it will be down the road, so try not start the name of the function will be built to help, so normal 10 00:00:38,890 --> 00:00:40,780 function is build the helper. 11 00:00:45,710 --> 00:00:47,720 So it will take in order traversal. 12 00:00:52,090 --> 00:00:54,010 So it will take in order to as input. 13 00:00:55,520 --> 00:00:56,390 It will take. 14 00:00:58,610 --> 00:01:00,050 Bulstrode traversal as input. 15 00:01:03,370 --> 00:01:08,500 And we know it will start in order to start Bulstrode around. 16 00:01:09,890 --> 00:01:10,370 So. 17 00:01:11,480 --> 00:01:12,130 In order. 18 00:01:13,440 --> 00:01:13,980 Start. 19 00:01:16,010 --> 00:01:17,300 In order and. 20 00:01:21,020 --> 00:01:21,720 Let's start. 21 00:01:24,580 --> 00:01:25,570 Bulstrode and. 22 00:01:26,970 --> 00:01:32,620 And this function will return the there and how we will call this function. 23 00:01:32,640 --> 00:01:36,510 So in the end is equal to the door, says. 24 00:01:42,300 --> 00:01:47,260 So you can also use Rhodes's size or poster or size, basically the number of elements will be seen. 25 00:01:47,970 --> 00:01:53,520 So in order that size and we will call this function will helper. 26 00:01:57,120 --> 00:01:59,040 So they've done very little helper. 27 00:01:59,940 --> 00:02:01,520 I will pass in order. 28 00:02:02,560 --> 00:02:03,910 I will pass in order, Eddie. 29 00:02:07,450 --> 00:02:11,320 So dysfunctioning need also that I also saw a post already. 30 00:02:13,960 --> 00:02:19,710 This function need to start in order, and so in order to start the index is zero in order and indexes 31 00:02:19,710 --> 00:02:22,860 and minus one Bulstrode start is zero. 32 00:02:23,700 --> 00:02:25,590 Order that and indexes and minus one. 33 00:02:27,170 --> 00:02:30,270 Simple, so now dysfunction is a recursive function. 34 00:02:30,560 --> 00:02:32,770 So first let us discuss about the case. 35 00:02:33,020 --> 00:02:41,040 So this case is basically empty and so far empty at the start will be greater than in order and order. 36 00:02:41,140 --> 00:02:42,590 You can also use Bulstrode. 37 00:02:42,590 --> 00:02:43,980 Astarte is guerdon order. 38 00:02:44,000 --> 00:02:48,470 And so that means ampitheater and for ampitheater military will be empty. 39 00:02:48,470 --> 00:02:49,490 I am returning then. 40 00:02:49,880 --> 00:02:51,140 So biscuits is now ready. 41 00:02:51,350 --> 00:02:52,890 And what is our approach? 42 00:02:53,270 --> 00:02:55,040 So let me write it here. 43 00:02:55,800 --> 00:02:57,220 Our approach is very simple. 44 00:02:57,740 --> 00:03:04,250 I want to I will create the root node and then I will colocation for building the left subtree. 45 00:03:04,250 --> 00:03:06,520 I will call the kitchen for building the right subtree. 46 00:03:06,980 --> 00:03:12,270 So for creating the root that we know we need to find out the root data and what is the root data. 47 00:03:12,380 --> 00:03:19,130 So in the post retriever's first we print the left Sabry then we print that I etc and then we print 48 00:03:19,130 --> 00:03:19,860 the root data. 49 00:03:20,120 --> 00:03:23,410 So the last element for the post traversal. 50 00:03:23,420 --> 00:03:25,250 So we need to find out the last element. 51 00:03:27,020 --> 00:03:28,940 So what is little data so integer? 52 00:03:31,090 --> 00:03:38,660 Raw data is basically the last element of the poster that said, let's copy this supposed order edit 53 00:03:38,680 --> 00:03:42,610 and we need to give the last index so you will give a boost and. 54 00:03:43,920 --> 00:03:44,680 So opposed. 55 00:03:44,700 --> 00:03:51,750 And so now we know the route data and we need to find out the values of the variables. 56 00:03:53,220 --> 00:03:56,700 So in detail, we need left in order to start. 57 00:03:59,060 --> 00:04:09,110 We need to find out left in order, and similarly, we need to find out left Bulstrode Astarte. 58 00:04:11,800 --> 00:04:18,820 Left both to end and similarly, the forward values for the right tree so that we can build the right 59 00:04:18,820 --> 00:04:22,900 subtree, so a right in order to start. 60 00:04:26,440 --> 00:04:28,690 Right, in order and. 61 00:04:32,670 --> 00:04:33,240 Right. 62 00:04:34,310 --> 00:04:35,240 Bulstrode Astarte. 63 00:04:36,830 --> 00:04:37,760 And right. 64 00:04:39,380 --> 00:04:45,020 And so if we will be able to find out all these great values, then what we can do. 65 00:04:45,030 --> 00:04:47,190 So first step was building the road. 66 00:04:47,210 --> 00:04:48,380 So we know the route data. 67 00:04:48,800 --> 00:04:49,370 We know the route. 68 00:04:50,000 --> 00:04:51,470 So let's build the road. 69 00:04:53,620 --> 00:04:54,910 So the North Star. 70 00:04:56,500 --> 00:04:57,010 Route. 71 00:04:58,470 --> 00:05:06,700 Is your DNA and we will pass the down, so now our Rudy is ready. 72 00:05:06,720 --> 00:05:13,360 So what we need to do after finding out the truth, after constructing the route, we will call, we 73 00:05:13,380 --> 00:05:16,190 will build the subtree and then we will build the right subtree. 74 00:05:16,350 --> 00:05:18,490 So first, let us build the SIPRI. 75 00:05:21,600 --> 00:05:28,080 So, Bill, the left subtree, so rude and left, is for building the left subtree with the help of 76 00:05:28,080 --> 00:05:28,710 this function. 77 00:05:30,370 --> 00:05:35,860 Military helper, I will give this in order that I need to pass the order ready. 78 00:05:39,220 --> 00:05:41,080 I need to pass postmodernity. 79 00:05:44,190 --> 00:05:48,700 I need to pass the start for the left, I'm calculating left. 80 00:05:49,140 --> 00:05:52,230 I am constructing left, so I will pass left in order to start. 81 00:05:55,490 --> 00:06:00,920 Then in order and so I'm constructing left subtree, so left in order and. 82 00:06:03,680 --> 00:06:12,410 Then left Bulstrode start because I'm building left subtree and left posterboard around because I'm 83 00:06:12,410 --> 00:06:17,370 building the left sempre so now your left the prison already. 84 00:06:18,230 --> 00:06:25,000 So now let us build our right subtree so we will take the help of this function military helper. 85 00:06:25,910 --> 00:06:29,570 Let's call this function so this function needs the ordinary. 86 00:06:30,050 --> 00:06:32,480 This function also needs the poster today. 87 00:06:34,680 --> 00:06:40,470 Then this function needs the start, since I'm building the right subtree, so I will give right in 88 00:06:40,470 --> 00:06:41,040 order to start. 89 00:06:43,030 --> 00:06:45,850 Then I will give right in order and. 90 00:06:49,800 --> 00:06:52,590 Then I will give right Bulstrode start. 91 00:06:55,700 --> 00:06:58,760 And then I will give right boaster and. 92 00:07:03,450 --> 00:07:06,830 So now what is a situation so I have constructed this route not. 93 00:07:07,930 --> 00:07:14,300 With the help of discord and then I am building that tree and I am passing the left in order that it 94 00:07:14,320 --> 00:07:15,550 and the left already. 95 00:07:15,590 --> 00:07:19,600 So this tree will be constructed and then I am making the connection. 96 00:07:19,600 --> 00:07:21,190 So connection has been established. 97 00:07:21,520 --> 00:07:24,310 Then I'm calling the function for building the right subtree. 98 00:07:24,490 --> 00:07:26,550 So I am passing right in order and right. 99 00:07:26,560 --> 00:07:26,930 Bulstrode. 100 00:07:27,280 --> 00:07:30,150 So this tree will be constructed and then I am attaching. 101 00:07:30,430 --> 00:07:32,530 So then this connection has been established. 102 00:07:32,650 --> 00:07:35,360 For now the tree is ready and we will return the room. 103 00:07:36,310 --> 00:07:37,550 So let's return the root. 104 00:07:39,230 --> 00:07:41,370 So now we will return that. 105 00:07:42,260 --> 00:07:43,680 So now everything is ready. 106 00:07:44,390 --> 00:07:46,910 The one thing left, so everything is ready. 107 00:07:46,950 --> 00:07:47,910 Everything will work fine. 108 00:07:47,930 --> 00:07:50,570 Now we need to find out these eight values. 109 00:07:51,530 --> 00:07:54,880 And we already collected these eight values in our previous video. 110 00:07:55,580 --> 00:07:59,420 So if you will see, these are the values we have calculated. 111 00:07:59,450 --> 00:08:00,880 OK, so let's put it. 112 00:08:01,040 --> 00:08:03,590 So what is left in order to start this is in order to start. 113 00:08:06,450 --> 00:08:07,950 So left in order to start. 114 00:08:09,070 --> 00:08:10,090 Is same as. 115 00:08:11,670 --> 00:08:12,510 In order to start. 116 00:08:17,380 --> 00:08:22,240 So what is left in order and it is the next minus one, we will find out through the next. 117 00:08:22,240 --> 00:08:23,680 Also, let's write it here. 118 00:08:24,370 --> 00:08:26,860 So next minus one. 119 00:08:30,240 --> 00:08:33,480 Left Bulstrode Astarte, so the system is supposed to restart. 120 00:08:35,429 --> 00:08:37,830 So this is Sam's story to start. 121 00:08:39,970 --> 00:08:43,510 So the system is supposed to restart left Bulstrode and. 122 00:08:44,780 --> 00:08:51,740 So left to right and left for the start, plus left in order and minus left in the start. 123 00:08:52,640 --> 00:08:55,520 So this is left Boston to start. 124 00:08:59,360 --> 00:09:00,860 Plus, left in order to end. 125 00:09:03,930 --> 00:09:06,870 Minus left in order to start. 126 00:09:09,940 --> 00:09:11,800 So what is riding on that start? 127 00:09:13,190 --> 00:09:15,740 Right, in order to start this route and express one. 128 00:09:17,360 --> 00:09:18,790 So we will tell you next. 129 00:09:18,860 --> 00:09:21,360 Also, first ladies right here. 130 00:09:21,380 --> 00:09:23,990 So this is routine X plus one. 131 00:09:26,370 --> 00:09:31,260 Right, in order and in order, and so this is in order and. 132 00:09:32,910 --> 00:09:36,060 So right in order and as Sams and. 133 00:09:38,830 --> 00:09:47,800 So what is right to restart the right, both to restart this left end, plus one left coast and plus 134 00:09:47,800 --> 00:09:50,770 one so left coast and plus one? 135 00:09:53,550 --> 00:09:54,150 Plus one. 136 00:09:56,390 --> 00:09:59,570 Right poster that this post and minus one. 137 00:10:00,820 --> 00:10:04,000 So this is post and minus one. 138 00:10:08,110 --> 00:10:14,200 So now we have the majority of the code, we have written the code for the majority of the problem. 139 00:10:15,550 --> 00:10:16,810 So now everything is ready. 140 00:10:17,080 --> 00:10:24,220 We just need to find out this root index so we'll find out the root index exactly like the previous 141 00:10:24,220 --> 00:10:24,560 problem. 142 00:10:24,600 --> 00:10:25,480 So what we need to do. 143 00:10:26,140 --> 00:10:28,170 So this is your order. 144 00:10:29,020 --> 00:10:36,140 So you have the left subtree, then the root and then the right separate. 145 00:10:36,160 --> 00:10:38,240 And what is the posterior traversal? 146 00:10:39,010 --> 00:10:45,240 So first your print left, then you print right subtree and then you print the root. 147 00:10:46,060 --> 00:10:48,490 So we have the root data, we have the root data. 148 00:10:48,730 --> 00:10:55,780 So we will search through data in the area so that all the time that area will be able to find out the 149 00:10:55,780 --> 00:10:56,380 root data. 150 00:10:56,560 --> 00:10:58,990 So this is called root index. 151 00:11:00,860 --> 00:11:03,100 So let's try to find out the truth the next. 152 00:11:05,770 --> 00:11:08,560 So let's find the root index so initially. 153 00:11:12,040 --> 00:11:16,960 The crude index is minus one now. 154 00:11:16,970 --> 00:11:22,900 We will trade over the area, so I will start from in order to start. 155 00:11:24,820 --> 00:11:28,450 I will search till in order and I placeless. 156 00:11:30,160 --> 00:11:30,940 So if. 157 00:11:32,670 --> 00:11:33,300 In order. 158 00:11:34,630 --> 00:11:37,330 So if in order I. 159 00:11:38,470 --> 00:11:40,390 Is it close to the true data? 160 00:11:43,510 --> 00:11:51,310 Then we know what is the root index, so index is a root index is a and we will break. 161 00:11:52,440 --> 00:11:54,840 So, again, I am repeating exactly the same thing. 162 00:11:55,170 --> 00:11:58,510 So our solution is assuming no duplicates. 163 00:11:59,160 --> 00:12:04,620 So the question also is duplicate does not exist because of duplicate exist, then our code will not 164 00:12:04,620 --> 00:12:04,900 work. 165 00:12:05,380 --> 00:12:10,790 OK, for example, if the data is for there are two forms in the room and in the left separate. 166 00:12:10,980 --> 00:12:12,600 So we will find out for here also. 167 00:12:12,810 --> 00:12:16,440 So basically you will not be able to construct or duplicate does not exist. 168 00:12:16,680 --> 00:12:18,210 And the input is right. 169 00:12:18,600 --> 00:12:25,470 If the input is wrong, basically the value of the next at this line, if the value of the index is 170 00:12:25,470 --> 00:12:26,180 still minus. 171 00:12:26,370 --> 00:12:30,900 That means your input is wrong and we will assume that the input is right. 172 00:12:31,770 --> 00:12:35,420 So I think that is the code that we need to write. 173 00:12:36,600 --> 00:12:39,960 So let's have a good first line of code and then we will submit. 174 00:12:44,070 --> 00:12:45,510 So in order to meet our goal. 175 00:12:48,910 --> 00:12:54,460 So, yes, basically, our goal is working success, so this is it from this video, I will see you 176 00:12:54,460 --> 00:12:55,210 in the next one. 177 00:12:55,240 --> 00:12:55,720 Thank you.