1 00:00:01,320 --> 00:00:03,000 Hi, everyone, welcome back. 2 00:00:03,060 --> 00:00:08,450 So in this video, we are going to discuss about discussion and our travels and of accommodation. 3 00:00:09,930 --> 00:00:12,690 So first of all, we know what is in traversal. 4 00:00:12,750 --> 00:00:16,160 It is you visit the left subtree first, then you visit the note. 5 00:00:16,170 --> 00:00:19,340 That is the data and then you visit denied Sabry. 6 00:00:19,860 --> 00:00:21,660 So left and right. 7 00:00:21,960 --> 00:00:24,300 And what is a Cartesian tree? 8 00:00:25,470 --> 00:00:29,100 So it is a good indication that this tree is a tree in which. 9 00:00:30,390 --> 00:00:38,070 Your route data will be the maximum data industry, so we have the subtree here, we have many nodes 10 00:00:38,070 --> 00:00:38,370 here. 11 00:00:40,470 --> 00:00:41,610 And so on. 12 00:00:45,800 --> 00:00:53,120 This is one tree, and it is given that basically the road data route will be the greatest, it will 13 00:00:53,120 --> 00:00:55,610 be the grid and all the elements and separate. 14 00:00:56,240 --> 00:00:58,450 So route will be the maximum value. 15 00:00:59,120 --> 00:01:02,180 And similarly, this property will hold for each and every node. 16 00:01:02,570 --> 00:01:09,360 So for this node, this node will contain the largest data of all the elements in its separate. 17 00:01:09,380 --> 00:01:12,140 Similarly for this node, similarly for this node. 18 00:01:12,140 --> 00:01:16,650 So this note will contain the largest data among all its subtree. 19 00:01:16,880 --> 00:01:20,360 So we are provided with these in order to have this tree. 20 00:01:21,380 --> 00:01:25,460 We are provided with and love this tree and we want to construct that tree. 21 00:01:26,060 --> 00:01:34,460 So given that traversal given the traversal it is left-to-right of this tree, we want to construct 22 00:01:34,460 --> 00:01:38,650 this tree and it is given that duplicates will not be there. 23 00:01:39,860 --> 00:01:47,480 So they are also providing us one example that if they are traversal is one, two and three, then this 24 00:01:47,480 --> 00:01:51,320 will be your Cartesian tree that you can see. 25 00:01:51,320 --> 00:01:55,430 Tree is basically larger than all the elements in the left and right. 26 00:01:55,440 --> 00:01:56,570 Separate does not exist. 27 00:01:56,840 --> 00:02:01,970 Similarly, element two is greater than all the elements in the left subtree and right separately for 28 00:02:01,970 --> 00:02:05,090 two does not exist, and for one, left and right does not exist. 29 00:02:05,540 --> 00:02:10,430 And the traversal for this will be one, two and three, which is correct. 30 00:02:10,430 --> 00:02:13,580 We can easily solve this question with the help of recursion. 31 00:02:13,580 --> 00:02:19,490 And in fact we have solved Tolkachev previously that given the order and the preordering reconstruct 32 00:02:19,490 --> 00:02:22,410 the tree given in order in order to reconstruct the tree. 33 00:02:22,700 --> 00:02:25,060 So this is going to be very similar to that only. 34 00:02:25,280 --> 00:02:27,800 So what we'll do let's is the screen 35 00:02:30,860 --> 00:02:33,470 and solving this problem is a cakewalk. 36 00:02:34,130 --> 00:02:35,630 Let's take one big example. 37 00:02:35,640 --> 00:02:41,460 Let's say I have this one, four, five, three, seven and nine. 38 00:02:41,480 --> 00:02:44,940 Let's say I have this Eddie and let's say I have zero. 39 00:02:45,170 --> 00:02:46,700 So all the elements are unique. 40 00:02:46,910 --> 00:02:48,110 Duplicates are not pleasant. 41 00:02:48,260 --> 00:02:51,830 And this is the trevathan traversal means left data. 42 00:02:51,830 --> 00:02:56,810 And right now we want to construct the Cartesian tree for this. 43 00:02:57,140 --> 00:02:58,560 So what will be our approach? 44 00:02:58,610 --> 00:03:01,610 So first of all, we will try to find out the root data. 45 00:03:02,360 --> 00:03:02,730 Right. 46 00:03:02,840 --> 00:03:05,070 So what is the maximum value? 47 00:03:05,480 --> 00:03:06,680 What is the maximum value? 48 00:03:07,190 --> 00:03:08,900 Nine is the maximum value. 49 00:03:09,410 --> 00:03:14,660 So that means nine will be my route, nine will be Darold. 50 00:03:15,620 --> 00:03:23,540 Then this all elements, these all elements will be the part of left Sabry and these all elements will 51 00:03:23,540 --> 00:03:24,440 be the part of Right. 52 00:03:24,450 --> 00:03:29,330 Sabry So in the right we have only one node so we can connect this now. 53 00:03:29,380 --> 00:03:30,830 Now let's talk about left. 54 00:03:31,370 --> 00:03:37,060 So again what we will call recursion on this and the collocation on this. 55 00:03:37,340 --> 00:03:40,010 So for this, what will happen again. 56 00:03:40,640 --> 00:03:42,290 What we will try to find out. 57 00:03:42,290 --> 00:03:53,960 The largest node, the largest node is seven to seven means seven will be the root node and all these 58 00:03:53,960 --> 00:03:58,010 elements will be the left of seven and right of seven does not exist. 59 00:03:58,010 --> 00:03:58,360 Right. 60 00:03:58,400 --> 00:04:00,530 So this is seven data is seven, right. 61 00:04:00,530 --> 00:04:01,310 Does not exist. 62 00:04:01,580 --> 00:04:04,810 And all the elements left of seven will be a part of separate. 63 00:04:04,850 --> 00:04:10,830 Again, industry five will be not because five is the maximum value. 64 00:04:11,240 --> 00:04:16,329 So five will be the road and right of seven will be none were discussed. 65 00:04:16,339 --> 00:04:16,740 Right. 66 00:04:18,019 --> 00:04:20,570 So four, five, four and one will be in the left. 67 00:04:20,930 --> 00:04:22,880 Three will be in the right sense. 68 00:04:23,330 --> 00:04:24,260 In the right hand side. 69 00:04:24,270 --> 00:04:27,740 We have only one node so we can construct one node. 70 00:04:27,740 --> 00:04:28,090 Right. 71 00:04:28,280 --> 00:04:29,990 And here we have two nodes. 72 00:04:29,990 --> 00:04:34,040 So the maximum is for the maximum is four. 73 00:04:34,040 --> 00:04:37,820 So four will be the data leftover will be delectability. 74 00:04:37,830 --> 00:04:41,480 So this is the last of three or four and I have three or four does not exist. 75 00:04:41,790 --> 00:04:42,650 So right. 76 00:04:42,650 --> 00:04:45,860 Is null and in left we have only one in order. 77 00:04:45,860 --> 00:04:50,830 So that will be this and this will be our Cartesian tree. 78 00:04:51,980 --> 00:04:53,320 Very, very simple, right. 79 00:04:54,320 --> 00:04:59,770 So we can see here, nine is bigger than all the elements in the left as well as right. 80 00:05:00,110 --> 00:05:02,530 Similarly, we can check this for any node. 81 00:05:02,810 --> 00:05:04,310 So I checking this for five. 82 00:05:04,310 --> 00:05:07,160 So four five left values are less right. 83 00:05:07,170 --> 00:05:08,390 Well you are also less. 84 00:05:09,260 --> 00:05:11,630 And what will be the traversal. 85 00:05:11,840 --> 00:05:14,370 So inheritance is left to right. 86 00:05:14,390 --> 00:05:22,280 So this will be first of all, I will visit one, then I will visit four, then I will visit five, 87 00:05:23,090 --> 00:05:27,080 then I will visit three, then visit seven, then nine and then zero. 88 00:05:27,470 --> 00:05:30,050 Then seven, then nine and then zero. 89 00:05:30,080 --> 00:05:30,470 Right. 90 00:05:32,540 --> 00:05:35,360 So let's discuss the final approach, what we need to do. 91 00:05:35,660 --> 00:05:43,460 So given this area, given the scenario, first of all, what I will do this is let's say I start. 92 00:05:43,760 --> 00:05:51,740 This is legit, and so I will I read it from start to end and I will try to find out the maximum data 93 00:05:51,740 --> 00:05:55,060 because the maximum data is going to be our root node. 94 00:05:55,520 --> 00:05:57,570 So let's say this is the maximum data. 95 00:05:59,510 --> 00:06:01,340 This is the maximum data. 96 00:06:01,640 --> 00:06:08,720 So what I will do, I will create one node containing the maximum data and then I will call that it 97 00:06:08,720 --> 00:06:09,990 goes in on the left hand side. 98 00:06:12,620 --> 00:06:16,870 So this will be the part of Lexapro I will call recursion on right hand side. 99 00:06:17,210 --> 00:06:23,620 These all elements will be the part of right subtree and how we can call. 100 00:06:23,930 --> 00:06:34,050 So for calling on the left, I will update and to be the index for this, let's say max index. 101 00:06:34,400 --> 00:06:38,380 So this really makes an X minus one and for calling on. 102 00:06:38,390 --> 00:06:38,930 Right. 103 00:06:39,200 --> 00:06:40,110 How will I call. 104 00:06:40,130 --> 00:06:48,070 So this is Max Index and this is the value of start will be the maximum index plus one and that's it. 105 00:06:49,610 --> 00:06:51,880 So this is going to be a recursive algorithm. 106 00:06:51,890 --> 00:06:56,720 And I already informed you, what will be the recursive relation rate for calling on left? 107 00:06:56,750 --> 00:06:59,690 This will be a start and this will be end for calling on, right. 108 00:06:59,720 --> 00:07:01,780 This will be start and this will be the end. 109 00:07:02,220 --> 00:07:03,320 Very simple code. 110 00:07:03,480 --> 00:07:07,250 So you can try to write the code for this column yourself. 111 00:07:07,250 --> 00:07:09,650 And the next video we will be writing the code. 112 00:07:10,310 --> 00:07:12,220 So this is all over this device. 113 00:07:12,230 --> 00:07:13,710 I will see you in the next one. 114 00:07:13,760 --> 00:07:14,360 Thank you.