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.

