1
00:00:00,900 --> 00:00:01,620
Hi, everyone.

2
00:00:01,650 --> 00:00:07,860
So in this video, we are going to discuss about the vertical ordered reversal of a binary tree, so

3
00:00:07,860 --> 00:00:09,440
what is a vertical ordered reversal?

4
00:00:09,450 --> 00:00:11,950
So we can understand this with the help of an example.

5
00:00:12,570 --> 00:00:14,600
So let's talk about this example.

6
00:00:14,760 --> 00:00:15,060
Right.

7
00:00:15,540 --> 00:00:17,670
So let me try it here.

8
00:00:17,670 --> 00:00:23,290
So I have three, then I have nine, and then I have 20.

9
00:00:23,880 --> 00:00:25,920
So this is 15.

10
00:00:26,780 --> 00:00:35,270
And then I have seven, right, so this is the tree and what happens in vertical reversal is basically

11
00:00:35,930 --> 00:00:38,030
this let me change the color.

12
00:00:38,250 --> 00:00:40,850
So see, this is one line.

13
00:00:41,300 --> 00:00:43,820
We are traversing the tree vertically.

14
00:00:44,930 --> 00:00:45,710
Second line.

15
00:00:47,090 --> 00:00:47,750
Third line.

16
00:00:49,310 --> 00:00:57,230
And fourth line, so in the first line, nine is present in the second lengthy and 59 percent, three

17
00:00:57,230 --> 00:01:03,250
and 15 in the third line, I have 20 and in the fourth line I have seven.

18
00:01:04,760 --> 00:01:05,950
So that is the output.

19
00:01:07,400 --> 00:01:10,060
So we need to traverse that three vertically.

20
00:01:12,770 --> 00:01:15,020
We want to traverse the tree vertically.

21
00:01:16,070 --> 00:01:18,980
Let's take one more example so that you can understand it better.

22
00:01:20,870 --> 00:01:22,560
Let's talk about this example.

23
00:01:24,770 --> 00:01:27,230
So here, let me draw that tree.

24
00:01:27,560 --> 00:01:32,990
So I have one, then I have to.

25
00:01:33,350 --> 00:01:34,810
And here I have three.

26
00:01:35,330 --> 00:01:36,980
So here I have four.

27
00:01:37,730 --> 00:01:39,170
Here I have five.

28
00:01:40,490 --> 00:01:44,890
Then I have six here and then I have seven here.

29
00:01:45,140 --> 00:01:48,560
So again, we will do we will draw the vertical line.

30
00:01:49,070 --> 00:01:56,280
So one vertical line and they will decline another vertical line, another and the last one.

31
00:01:57,140 --> 00:01:59,030
So on the first vertical line I have four.

32
00:02:00,620 --> 00:02:02,360
On the second vertical line I have two.

33
00:02:03,500 --> 00:02:06,460
On the third vertical line I have three elements, one, five and six.

34
00:02:07,580 --> 00:02:10,490
So I have three elements, one, five and six.

35
00:02:10,850 --> 00:02:13,640
On the fourth vertical line, I have only one entry.

36
00:02:14,000 --> 00:02:16,580
And here I have only one element, which is seven.

37
00:02:16,580 --> 00:02:17,870
And that is your output.

38
00:02:19,430 --> 00:02:19,820
Right.

39
00:02:20,640 --> 00:02:21,980
Let's take one more example.

40
00:02:23,300 --> 00:02:24,600
So I think they have provided.

41
00:02:24,980 --> 00:02:27,140
So we have one more example.

42
00:02:27,890 --> 00:02:30,650
And again, let's not agree.

43
00:02:31,340 --> 00:02:34,820
So I have one here, then I have two.

44
00:02:35,360 --> 00:02:36,620
Then I have four.

45
00:02:37,250 --> 00:02:38,810
Then I have six here.

46
00:02:39,410 --> 00:02:45,020
So I have three here, I have five here and I have seven here.

47
00:02:45,830 --> 00:02:47,840
And now let's draw the vertical lines.

48
00:02:47,930 --> 00:02:52,010
First vertical line, second vertical line tower vertical line.

49
00:02:52,010 --> 00:02:54,500
Fourth vertical line and fifth vertical line.

50
00:02:56,300 --> 00:03:00,980
So on the first vertical line, I have only one element, and it is four on the second vertical line,

51
00:03:00,990 --> 00:03:02,490
I have only one element, that is two.

52
00:03:02,760 --> 00:03:06,860
On the third vertical line, I have three elements, one, six and five.

53
00:03:07,380 --> 00:03:11,460
And here I have elementary and here I have elements seven.

54
00:03:12,220 --> 00:03:16,840
So if you really compare these two, so the only thing that is different is basically this one.

55
00:03:17,190 --> 00:03:20,670
So here this thing went five, six and I am writing one six five.

56
00:03:20,940 --> 00:03:23,820
So it is given in the question, in the question.

57
00:03:23,820 --> 00:03:28,070
They are saying that when you're returning the output, return the output unsorted a minute.

58
00:03:28,980 --> 00:03:31,210
So what will do before returning the answer?

59
00:03:32,050 --> 00:03:34,950
So before returning the answer, we will start each and every element.

60
00:03:34,980 --> 00:03:36,540
So it is containing one element.

61
00:03:36,550 --> 00:03:40,100
So don't do anything, one element, don't do anything.

62
00:03:40,110 --> 00:03:42,150
And here it is containing more than one element.

63
00:03:42,160 --> 00:03:46,050
So we will start and then we will return three and seven.

64
00:03:46,310 --> 00:03:46,680
Right.

65
00:03:46,890 --> 00:03:49,290
So days when one element or nothing.

66
00:03:49,680 --> 00:03:51,240
So don't need to do anything.

67
00:03:51,690 --> 00:03:55,600
So this extra thing that is unit to return, you are put in a certain amount.

68
00:03:56,070 --> 00:03:57,440
This is given in the equation.

69
00:03:57,450 --> 00:04:02,430
So that's why before returning the answer one six five, I will start and then I will return one five

70
00:04:02,430 --> 00:04:02,760
six.

71
00:04:03,910 --> 00:04:07,630
So I hope you have understood what is particularly traversal right.

72
00:04:08,010 --> 00:04:09,550
This thing is clear to you now.

73
00:04:10,470 --> 00:04:14,220
So now the question comes how we can solve this problem.

74
00:04:14,730 --> 00:04:21,649
So what I will do I will explain you everything in this video and you will try to write the code yourself.

75
00:04:21,660 --> 00:04:24,400
And in the next video, we will be writing the code.

76
00:04:24,690 --> 00:04:26,160
So what will happen?

77
00:04:26,580 --> 00:04:29,760
The logic to solve this problem is really, really very simple.

78
00:04:30,820 --> 00:04:35,610
So what they will do, so let me do one thing, I have three here, let me try again.

79
00:04:35,770 --> 00:04:41,620
Nine, I have 20 here, I have 15 here and I have seven here.

80
00:04:42,730 --> 00:04:44,830
So I will create one map.

81
00:04:46,450 --> 00:04:52,990
So this map will be horizontal distance versus list.

82
00:04:54,910 --> 00:05:03,340
So horizontal distance will be one integer and list, obviously, you need to create one array or create

83
00:05:03,340 --> 00:05:04,630
one vector list, right?

84
00:05:05,070 --> 00:05:07,720
So this will be my key and this will be my value.

85
00:05:08,980 --> 00:05:10,630
So what is this horizontal distance?

86
00:05:10,660 --> 00:05:11,590
Let me explain you.

87
00:05:11,890 --> 00:05:13,720
What do I mean by horizontal distance?

88
00:05:14,160 --> 00:05:16,940
So a root node, horizontal distance, zero.

89
00:05:17,770 --> 00:05:24,160
So whenever you will go left, you will reduce horizontal distance that is horizontal distance, minus

90
00:05:24,160 --> 00:05:24,580
minus.

91
00:05:24,910 --> 00:05:28,890
And whenever you will go right, you will go horizontal distance plus place.

92
00:05:29,170 --> 00:05:30,250
So let's do with me.

93
00:05:30,790 --> 00:05:33,490
This is three in and I am going left.

94
00:05:33,790 --> 00:05:36,340
So horizontal distance for this is minus one.

95
00:05:37,680 --> 00:05:38,530
Let's go here.

96
00:05:38,750 --> 00:05:43,000
So from zero horizontal distance plus plus horizontal distance is one.

97
00:05:43,390 --> 00:05:48,820
If I will go right again then horizontal distance plus plus lattice or the distance will become two.

98
00:05:49,120 --> 00:05:52,430
So if I will go here then I'm going left.

99
00:05:52,900 --> 00:05:53,440
Degrees.

100
00:05:53,500 --> 00:05:56,740
So from when the horizontal distance will become zero.

101
00:05:57,010 --> 00:05:59,410
So now we're going to do so for this node.

102
00:05:59,410 --> 00:06:00,970
The horizontal distance is minus one.

103
00:06:01,000 --> 00:06:08,090
So I was told in a map like this horizontal distance minus one, and I have only one node whose horizontal

104
00:06:08,110 --> 00:06:09,160
distances minus one.

105
00:06:09,760 --> 00:06:12,550
Now let's talk about zero before zero.

106
00:06:12,580 --> 00:06:13,910
I have actually two nodes.

107
00:06:14,200 --> 00:06:17,400
This is the first node, which is horizontal distance and zero.

108
00:06:17,410 --> 00:06:20,570
And for this note, also horizontal distance zero.

109
00:06:20,830 --> 00:06:26,760
So I will write three and 15 here now, horizontal distance one.

110
00:06:27,400 --> 00:06:31,180
So I have horizontal distance one and only one node.

111
00:06:31,600 --> 00:06:36,910
Again, I have horizontal distance two and the node is seven.

112
00:06:37,700 --> 00:06:38,110
Right.

113
00:06:38,290 --> 00:06:43,580
So your map will be ready and how you can prepare this map.

114
00:06:43,600 --> 00:06:44,410
So what to do?

115
00:06:44,410 --> 00:06:46,150
You need to do level order traversal.

116
00:06:48,760 --> 00:06:56,800
You will do level order traversal and after doing the level order traversal your map will be ready and

117
00:06:56,800 --> 00:07:00,190
for doing traversal what we need, we need when you.

118
00:07:01,420 --> 00:07:08,590
So earlier, we used to have you of note, right, we only saw the note, but right now we noticed two

119
00:07:08,590 --> 00:07:12,160
things will to the node as well as the horizontal distance.

120
00:07:12,490 --> 00:07:14,230
So you will store two things.

121
00:07:14,710 --> 00:07:18,940
It will store your node and it will store your horizontal distance.

122
00:07:19,300 --> 00:07:22,940
So what you can do, you can make one class that is containing these two variables.

123
00:07:23,410 --> 00:07:27,520
So after doing the level traversal with the help of your map will be ready.

124
00:07:29,430 --> 00:07:35,740
Your map will be ready and then what do you need to iterate over the map, you will.

125
00:07:36,240 --> 00:07:41,030
So the first value is nine, so you will put the answer that the answer is nine.

126
00:07:41,070 --> 00:07:42,740
Now, the next is three and 15.

127
00:07:43,320 --> 00:07:45,120
So the next is three and 15.

128
00:07:45,390 --> 00:07:46,640
The next one is 20.

129
00:07:46,650 --> 00:07:48,000
So you will put 20.

130
00:07:48,360 --> 00:07:49,650
The next one is seven.

131
00:07:49,650 --> 00:07:50,990
So you will put seven.

132
00:07:51,000 --> 00:07:53,670
And that is your answer, right.

133
00:07:53,850 --> 00:07:58,100
So what do you need to return a unit to return vector of veteran teachers?

134
00:07:58,890 --> 00:08:06,420
So this is a vector of individuals, vector of integers, integers, vector of integers and a big vector.

135
00:08:07,380 --> 00:08:09,170
But that's how you can solve this question.

136
00:08:09,180 --> 00:08:15,510
You just need to do traversal and fordoing level or traversal unit to store two things node as well

137
00:08:15,510 --> 00:08:16,830
as the horizontal distance.

138
00:08:17,490 --> 00:08:24,990
And then your map will contain horizontal distance to basically list of nodes that are corresponding

139
00:08:24,990 --> 00:08:26,430
to this horizontal distance.

140
00:08:26,940 --> 00:08:28,500
So let me take one more example.

141
00:08:29,390 --> 00:08:40,850
And to make myself clear, let me draw the tree again, so I have one here, then two, then four,

142
00:08:42,559 --> 00:08:52,910
then I have five here, so I have three here, I have seven here, sorry, six here and I have seven

143
00:08:52,910 --> 00:08:53,170
here.

144
00:08:53,750 --> 00:08:56,590
Now, again, horizontal distance is zero.

145
00:08:56,600 --> 00:08:57,460
I'm going left.

146
00:08:57,470 --> 00:09:01,990
So for this minus I'm going left for this minus two I'm going right.

147
00:09:02,000 --> 00:09:03,320
So it will become zero.

148
00:09:03,680 --> 00:09:04,690
I'm going right.

149
00:09:04,700 --> 00:09:05,510
So it will increase.

150
00:09:05,510 --> 00:09:06,200
I'm going right.

151
00:09:06,200 --> 00:09:06,950
It will increase.

152
00:09:06,950 --> 00:09:07,790
I'm going left.

153
00:09:07,790 --> 00:09:08,590
It will decrease.

154
00:09:09,380 --> 00:09:12,110
So now we have the horizontal distance for every node.

155
00:09:12,320 --> 00:09:12,740
Right.

156
00:09:13,040 --> 00:09:15,860
So when we are doing level traversal we will prepare the map.

157
00:09:18,100 --> 00:09:25,990
And in this map, we will have horizontal distance to the list of nodes, so horizontal distance four

158
00:09:25,990 --> 00:09:33,420
minus two, so four minus two, I have only one node, which is four for central distance, minus one.

159
00:09:33,430 --> 00:09:35,080
I have only one node, which is two.

160
00:09:37,140 --> 00:09:38,570
Four zero.

161
00:09:38,700 --> 00:09:43,750
I have three nodes, actually, this node, this node and this node.

162
00:09:44,880 --> 00:09:54,210
So one, five and six for this horizontal distance one I have only one node, which is three for horizontal

163
00:09:54,210 --> 00:09:54,880
distance two.

164
00:09:55,890 --> 00:09:57,700
I have only one node, which is seven.

165
00:09:58,320 --> 00:10:03,580
So by doing the level of the traversal, you will be able to prepare this map.

166
00:10:04,350 --> 00:10:06,090
You will be able to populate this map.

167
00:10:06,090 --> 00:10:09,980
And once your map is ready, you need to iterate over your map.

168
00:10:10,860 --> 00:10:14,170
You will read all the map and we have the answer.

169
00:10:14,190 --> 00:10:17,720
So first is for you can see for next is two.

170
00:10:18,060 --> 00:10:19,080
So I have two here.

171
00:10:19,260 --> 00:10:20,660
Next is one, five, six.

172
00:10:20,670 --> 00:10:21,300
So I have one.

173
00:10:21,300 --> 00:10:21,840
Five, six.

174
00:10:22,230 --> 00:10:23,110
Next three.

175
00:10:23,160 --> 00:10:23,850
I have three.

176
00:10:24,390 --> 00:10:25,260
Nexus seven.

177
00:10:25,270 --> 00:10:26,200
So I have seven.

178
00:10:26,490 --> 00:10:29,010
So basically this approach is going to work.

179
00:10:29,520 --> 00:10:30,510
Very easy question.

180
00:10:31,050 --> 00:10:40,080
You just need to do order traversal and while doing the level traversal the cuvee start putting it to

181
00:10:40,110 --> 00:10:44,370
the node and it will store the horizontal distance for that node.

182
00:10:45,210 --> 00:10:50,130
And then you need to do simple level or traversal and it will insert the values in the map.

183
00:10:51,300 --> 00:10:58,200
And once the level traversal is completed, you need to redraw the map and you need to populate your

184
00:10:58,200 --> 00:10:58,640
answer.

185
00:10:59,070 --> 00:11:00,090
Very simple logic.

186
00:11:00,090 --> 00:11:04,140
And the code is also going to be very, very simple, if you will follow each and every step.

187
00:11:04,560 --> 00:11:08,190
So in the next video, we will be writing the code for this problem.

188
00:11:08,370 --> 00:11:09,970
And I will see you in the next one.

189
00:11:10,290 --> 00:11:10,860
Thank you.