1
00:00:01,070 --> 00:00:01,730
Hi, everyone.

2
00:00:01,760 --> 00:00:05,300
So in this video, let us discuss what is posted at traversal.

3
00:00:06,540 --> 00:00:14,430
OK, so suppose you have this root node, then you have the left subtree and you have the right subtree.

4
00:00:15,210 --> 00:00:21,300
So Bulstrode Traversal says first you visit the left subtree, then you visit that I had subtree and

5
00:00:21,300 --> 00:00:23,580
then you visit the data of the root node.

6
00:00:23,610 --> 00:00:26,850
OK, so NRD left subtree right.

7
00:00:27,240 --> 00:00:29,400
And the date of the root node, very simple.

8
00:00:29,430 --> 00:00:33,510
OK, now let us apply the poster trevisan on this by Nutri.

9
00:00:33,720 --> 00:00:41,880
OK, so first left, this will be number one and then the right separates or two and number three,

10
00:00:41,910 --> 00:00:42,870
which is the data.

11
00:00:43,120 --> 00:00:46,650
OK, so it will be basically left subtree.

12
00:00:48,390 --> 00:00:51,690
Right subtree and so so five to.

13
00:00:53,110 --> 00:00:55,060
OK, so when is completed?

14
00:00:55,090 --> 00:00:56,140
Now let's go for two.

15
00:00:56,170 --> 00:01:00,120
So this is only three, so likely three and two is visited.

16
00:01:00,220 --> 00:01:02,440
So let's go to number three one.

17
00:01:02,620 --> 00:01:06,640
OK, so this is the Beausoleil traversal for Destry.

18
00:01:07,840 --> 00:01:13,690
Now, let us discuss the post-war traversal for Destry, very simple left right data, so left does

19
00:01:13,690 --> 00:01:14,290
not exist.

20
00:01:14,710 --> 00:01:20,700
Now let's go to right, OK, so left three right does not exist data.

21
00:01:20,890 --> 00:01:22,020
So left right data.

22
00:01:22,060 --> 00:01:22,840
So three, two.

23
00:01:22,840 --> 00:01:23,510
And then one.

24
00:01:24,640 --> 00:01:27,300
So this is the poster traversal for distri.

25
00:01:28,300 --> 00:01:30,940
Now let us write the poster traversal for distri.

26
00:01:30,940 --> 00:01:32,820
OK, I remember left right data.

27
00:01:33,550 --> 00:01:39,100
OK, so left right data for 2010.

28
00:01:40,750 --> 00:01:49,060
Simple again, left right data, so this will be 18, 24, 22, then 15.

29
00:01:51,270 --> 00:01:54,840
So left is completed now let's go for the ride.

30
00:01:54,840 --> 00:02:06,990
Sabry so left right data So this will be 31, 44 and 35 again left right data to this will be 66, 90

31
00:02:07,710 --> 00:02:08,610
and 70.

32
00:02:09,120 --> 00:02:09,900
Then 50.

33
00:02:10,639 --> 00:02:11,760
OK, so 50.

34
00:02:12,790 --> 00:02:17,380
Now, the rights are pretty complicated, so left is completely dry, discomfited now data.

35
00:02:17,410 --> 00:02:20,330
OK, so left, right and data.

36
00:02:20,350 --> 00:02:21,420
So now 25.

37
00:02:22,360 --> 00:02:26,140
OK, so this is the poster traversal for this by Nutri.

38
00:02:27,490 --> 00:02:28,960
So I hope you understood the logic.

39
00:02:29,140 --> 00:02:30,070
Let us ride the cold.

40
00:02:30,100 --> 00:02:31,530
So cold will be very, very simple.

41
00:02:32,170 --> 00:02:33,790
So let's say you have a function visit.

42
00:02:34,070 --> 00:02:38,730
So this visit function will take root as input and what it will do.

43
00:02:39,010 --> 00:02:40,560
So first of all, left subtree.

44
00:02:40,570 --> 00:02:47,640
So I will visit the left subtree, then I will visit the right subtree, left right data.

45
00:02:48,430 --> 00:02:50,090
So let us visit the right separate.

46
00:02:50,170 --> 00:02:54,970
And then finally I can directly, I can print, I can visit the data.

47
00:02:55,150 --> 00:02:57,100
OK, so very simple.

48
00:02:58,280 --> 00:02:59,980
Left right data.

49
00:03:00,020 --> 00:03:00,920
So this is left.

50
00:03:01,190 --> 00:03:05,060
This is right and this is data, OK, very, very simple.

51
00:03:05,090 --> 00:03:06,290
Now, let us write the gold.

52
00:03:07,740 --> 00:03:13,470
OK, so again, if this is Nedry, this is the poster traversal three to one.

53
00:03:13,770 --> 00:03:16,140
OK, now let's write the code.

54
00:03:16,140 --> 00:03:21,720
So first we will write the simple code for post water and then we will modify the code according to

55
00:03:21,720 --> 00:03:22,290
the question.

56
00:03:22,330 --> 00:03:22,650
OK.

57
00:03:27,950 --> 00:03:29,440
So first of all, the base case.

58
00:03:29,450 --> 00:03:33,470
So if rotational, that means the crew did not exist.

59
00:03:33,470 --> 00:03:34,800
So you can basically done.

60
00:03:34,890 --> 00:03:35,230
OK.

61
00:03:37,170 --> 00:03:42,060
Then I have to follow the order left right data, so both order.

62
00:03:45,500 --> 00:03:45,950
Left.

63
00:03:47,590 --> 00:03:48,370
Dendrite.

64
00:03:59,870 --> 00:04:01,510
So left, right, and then later.

65
00:04:07,450 --> 00:04:08,780
OK, so very, very simple.

66
00:04:08,800 --> 00:04:13,900
So this is the code for BORSTAR Driesell, first left, then right and then later.

67
00:04:14,280 --> 00:04:18,620
OK, so in this question I have to return the property just so there's no need to print.

68
00:04:19,000 --> 00:04:20,260
So again, I will create.

69
00:04:21,420 --> 00:04:27,340
A vector of integers, let's say the name of the vector is answer, I will call it the function Bulstrode.

70
00:04:29,610 --> 00:04:34,710
I will give the road Nordhausen, but I will give them three years in port and I will give the answer

71
00:04:34,710 --> 00:04:38,190
Victor and finally I will return my answer.

72
00:04:38,640 --> 00:04:46,950
OK, now let us modify the function so it will take a vector of integers as input and obviously by reference,

73
00:04:47,460 --> 00:04:48,840
the name of the vector is answer.

74
00:04:48,880 --> 00:04:54,660
OK, so instead of and here I have to modify so I will pass answer.

75
00:04:56,310 --> 00:05:02,070
And answer, and instead of printing the value, I will store it in the onset of that.

76
00:05:02,130 --> 00:05:03,210
OK, Sir Lancelot.

77
00:05:04,340 --> 00:05:04,910
Bushwack.

78
00:05:07,040 --> 00:05:07,490
Well, you.

79
00:05:09,050 --> 00:05:11,510
OK, so let's run and then we will submit.

80
00:05:16,180 --> 00:05:17,350
OK, now let's meet.

81
00:05:22,040 --> 00:05:27,050
OK, so level code is working fine now let us discuss the timing, the space complexity for the postal

82
00:05:27,060 --> 00:05:27,470
address.

83
00:05:27,990 --> 00:05:34,790
OK, so again, that time complexity is basically big often as we have to visit each and every node

84
00:05:34,940 --> 00:05:37,820
and the space complexity in the worst cases big often.

85
00:05:37,850 --> 00:05:40,880
OK, so this is complexity is due to the collision course.

86
00:05:41,180 --> 00:05:42,320
So it is due to the collision.

87
00:05:42,980 --> 00:05:43,370
OK.

88
00:05:44,600 --> 00:05:49,010
And is the number of nodes, total number of nodes presently by Nutri?

89
00:05:49,070 --> 00:05:53,150
OK, now let us compare all the traversal.

90
00:05:53,450 --> 00:05:56,840
OK, so, you know, traversal traversal and Beausoleil traversal.

91
00:05:57,380 --> 00:06:00,280
OK, so what is in order traversal.

92
00:06:01,250 --> 00:06:05,840
So in order to wss first you visit left then data and then right.

93
00:06:05,870 --> 00:06:09,740
OK, so left-to-right what is preorder traversal.

94
00:06:10,310 --> 00:06:15,110
So Purita is first you visit data, then you go for left and then you go for.

95
00:06:15,260 --> 00:06:15,460
Right.

96
00:06:15,740 --> 00:06:19,190
OK, so basically if you see carefully this is top down approach.

97
00:06:21,320 --> 00:06:23,120
We are visiting from top to down.

98
00:06:23,180 --> 00:06:24,500
OK, so if you have a tree.

99
00:06:25,540 --> 00:06:28,480
You have you have you have left and then you have right.

100
00:06:28,510 --> 00:06:31,910
So what I am doing first data and then left and then right.

101
00:06:31,930 --> 00:06:33,760
So basically this top down approach.

102
00:06:33,970 --> 00:06:35,970
OK, I'm going from top to bottom.

103
00:06:36,700 --> 00:06:38,920
Now, the third one, which is the poster that.

104
00:06:42,040 --> 00:06:46,090
So this is first who is it left, then who was it right and then who is it?

105
00:06:46,090 --> 00:06:46,570
Data.

106
00:06:46,670 --> 00:06:50,170
OK, so if you see carefully, this is bottom up approach.

107
00:06:51,790 --> 00:06:53,110
This is bottom up.

108
00:06:53,180 --> 00:07:01,390
OK, you have RWD, you have the left subtree, you have the right subtree and what you are doing left

109
00:07:01,390 --> 00:07:02,230
right data.

110
00:07:02,250 --> 00:07:07,870
So first I will visit the left, then I will visit the right, and then I will move ahead, move up

111
00:07:07,870 --> 00:07:09,190
and then I will visit route.

112
00:07:09,240 --> 00:07:10,960
OK, so this is bottom up.

113
00:07:11,860 --> 00:07:13,630
So I'm repeating myself in order.

114
00:07:13,630 --> 00:07:14,410
It is very simple.

115
00:07:14,680 --> 00:07:18,130
You visit the left, then data and then right subtree.

116
00:07:18,160 --> 00:07:21,310
OK, so Eliade preorder is very simple again.

117
00:07:21,880 --> 00:07:22,690
Data left.

118
00:07:22,690 --> 00:07:23,120
Right.

119
00:07:23,170 --> 00:07:30,350
This is top down approach because first I am visiting the top node and then I'm going down ok.

120
00:07:30,400 --> 00:07:35,170
I am going down and I'm printing the left and the right post today is different.

121
00:07:35,470 --> 00:07:38,250
So Postgres left right data.

122
00:07:38,530 --> 00:07:39,670
So this is Bottom-Up.

123
00:07:39,730 --> 00:07:45,100
Why this is a Bottom-Up because first you are visiting the left subtree, then you are visiting the

124
00:07:45,100 --> 00:07:47,250
right subtree and then you are visiting up.

125
00:07:47,680 --> 00:07:49,420
OK, so very simple.

126
00:07:49,420 --> 00:07:50,770
This is a top down approach.

127
00:07:50,770 --> 00:07:54,070
This is bottom up approach and this is simple.

128
00:07:54,220 --> 00:07:55,190
Left, right.

129
00:07:55,520 --> 00:08:02,850
OK, and the time and space complexity for all the three approaches is basically big often and big often.

130
00:08:02,890 --> 00:08:08,350
OK, so this is team, you know, traversal traversal and boaster traversal.

131
00:08:08,710 --> 00:08:12,460
OK, so these are two different types of traversal that we can perform.

132
00:08:14,130 --> 00:08:15,900
OK, thank you.

