1
00:00:00,000 --> 00:00:07,933
[No Audio]

2
00:00:07,934 --> 00:00:10,133
Consider a business which has a software for

3
00:00:10,134 --> 00:00:12,733
conducting online meetings of its employees.

4
00:00:13,166 --> 00:00:15,033
The company wants to keep track and display

5
00:00:15,034 --> 00:00:16,833
the list of participants attending the

6
00:00:16,834 --> 00:00:18,966
meeting using a suitable data structure.

7
00:00:18,967 --> 00:00:22,166
The company wants the names of the attendees in a

8
00:00:22,167 --> 00:00:24,500
meeting to be displayed in an alphabetical

9
00:00:24,501 --> 00:00:27,533
order. The attendees can join or leave a

10
00:00:27,534 --> 00:00:29,800
meeting at random, so the underlying data

11
00:00:29,801 --> 00:00:32,966
structure should allow for easy updation accordingly.

12
00:00:32,967 --> 00:00:35,166
After analyzing the problem, the

13
00:00:35,167 --> 00:00:37,633
designer team has agreed that the name of the

14
00:00:37,634 --> 00:00:40,000
attendees should be stored using a binary

15
00:00:40,001 --> 00:00:43,633
search tree. Once the names are stored, the

16
00:00:43,634 --> 00:00:46,200
company is further interested in a special

17
00:00:46,201 --> 00:00:48,633
mode of display called gallery mode.

18
00:00:48,634 --> 00:00:50,700
This display will allow the names of the

19
00:00:50,701 --> 00:00:53,300
participants to be shown in paginated form,

20
00:00:53,566 --> 00:00:55,833
that is divided into pages that can be

21
00:00:55,834 --> 00:00:58,633
scrolled down. In this scenario, we will

22
00:00:58,634 --> 00:01:01,533
assume that only 10 participant can be shown

23
00:01:01,534 --> 00:01:04,366
on one page. Our job is to use the binary

24
00:01:04,367 --> 00:01:05,866
search tree containing the names of the

25
00:01:05,867 --> 00:01:08,266
participants and implement the pagination.

26
00:01:08,633 --> 00:01:11,600
Whenever our function is called the names

27
00:01:11,601 --> 00:01:13,633
of the next 10 participants should be

28
00:01:13,634 --> 00:01:16,666
returned in an alphabetical order. Let us

29
00:01:16,667 --> 00:01:18,266
further elaborate the problem using

30
00:01:18,267 --> 00:01:20,466
PowerPoint slides for a better understanding.

31
00:01:21,733 --> 00:01:23,666
Consider this to be the binary search tree

32
00:01:23,667 --> 00:01:26,000
corresponding to the participants. The

33
00:01:26,001 --> 00:01:28,266
details of the binary search tree are already

34
00:01:28,267 --> 00:01:31,233
covered in the same section, so we will not

35
00:01:31,266 --> 00:01:33,533
be digging deep into the details. We will

36
00:01:33,534 --> 00:01:35,466
however repeat the main characteristic or

37
00:01:35,467 --> 00:01:37,733
property, which is that for each node, the

38
00:01:37,734 --> 00:01:40,900
left subtree of that node will contains all

39
00:01:40,901 --> 00:01:43,200
the values that are lesser than the value of

40
00:01:43,201 --> 00:01:45,700
the node itself. And the right subtree of the

41
00:01:45,701 --> 00:01:48,300
node will contain nodes whose values are

42
00:01:48,333 --> 00:01:50,566
greater than the value of the node. Please

43
00:01:50,567 --> 00:01:52,166
note that, in this case, the values are

44
00:01:52,167 --> 00:01:55,166
characters and not numbers. In order to

45
00:01:55,167 --> 00:01:57,000
compare two values, we will use their

46
00:01:57,001 --> 00:01:59,500
alphabetical order to determine whether one

47
00:01:59,501 --> 00:02:01,600
value is greater than the other or lesser

48
00:02:01,633 --> 00:02:04,366
than the other. Generally speaking, an

49
00:02:04,367 --> 00:02:06,833
alphabet which comes first is lesser than the

50
00:02:06,834 --> 00:02:09,333
alphabet which comes later. If the first

51
00:02:09,334 --> 00:02:12,700
letters of the names are the same, then we

52
00:02:12,701 --> 00:02:14,666
will compare based on the second letters, and

53
00:02:14,667 --> 00:02:17,600
so on. The function for the pagination will

54
00:02:17,601 --> 00:02:19,700
take this binary search tree as an input, and

55
00:02:19,701 --> 00:02:22,300
will produce the first 10 names from the tree

56
00:02:22,301 --> 00:02:24,733
as an output in an alphabetical order.

57
00:02:24,866 --> 00:02:27,400
In this case, it will produce this list of

58
00:02:27,401 --> 00:02:29,800
names. The second call to the function will

59
00:02:29,801 --> 00:02:32,533
produce the remaining names. Please note that

60
00:02:32,534 --> 00:02:34,466
since in binary search tree the values are

61
00:02:34,467 --> 00:02:37,166
stored in an effective order, therefore,

62
00:02:37,167 --> 00:02:39,033
retrieving the values in an alphabetical

63
00:02:39,034 --> 00:02:41,400
order will be easy. We will see this in a

64
00:02:41,401 --> 00:02:44,200
while. In summary, we need to implement a

65
00:02:44,201 --> 00:02:46,766
pagination or display function, which will

66
00:02:46,800 --> 00:02:48,566
display the values of the first 10

67
00:02:48,567 --> 00:02:50,966
participants retrieved from the binary search

68
00:02:50,967 --> 00:02:53,466
tree. Let us now explain our approach to

69
00:02:53,467 --> 00:02:56,033
solving this problem. Our solution will

70
00:02:56,034 --> 00:03:00,000
contain three key functions namely, Push_all_left,

71
00:03:00,001 --> 00:03:03,866
Next_name, and Next_page. The Push_all_left

72
00:03:03,867 --> 00:03:06,233
when called for a certain node, will push

73
00:03:06,266 --> 00:03:09,166
all the left nodes of that node in a stack.

74
00:03:09,933 --> 00:03:12,000
This function will only terminate when there

75
00:03:12,001 --> 00:03:14,633
are no more left nodes to push onto the stack.

76
00:03:15,333 --> 00:03:17,166
The Next_name function will return the

77
00:03:17,167 --> 00:03:19,466
next name in alphabetical order from the

78
00:03:19,467 --> 00:03:22,500
tree. It will be called 10 times since we

79
00:03:22,533 --> 00:03:25,766
since we want to retrieve 10 names per page.

80
00:03:25,966 --> 00:03:28,200
More specifically, it will do two things.

81
00:03:28,400 --> 00:03:30,866
Firstly, it will pop or remove the top

82
00:03:30,867 --> 00:03:33,333
element or node from the stack, and then it

83
00:03:33,334 --> 00:03:37,300
will call the Push_all_left on the right

84
00:03:37,301 --> 00:03:39,900
child of the removed element from the stack.

85
00:03:40,166 --> 00:03:42,366
This means that it will push the right child,

86
00:03:42,400 --> 00:03:45,566
and all the leftmost child of the right child

87
00:03:45,567 --> 00:03:48,133
onto the stack. Finally, the Next_page

88
00:03:48,134 --> 00:03:50,833
function will call the Next_name function 10

89
00:03:50,834 --> 00:03:53,633
times to retrieve the required names from the

90
00:03:53,634 --> 00:03:57,300
BST or binary search tree. All this may not

91
00:03:57,301 --> 00:03:59,633
be very clear for now, so let us dive a bit

92
00:03:59,634 --> 00:04:01,733
deep and see the solution in visual form.

93
00:04:02,566 --> 00:04:05,133
Consider this to be the input BST or binary

94
00:04:05,134 --> 00:04:08,033
search tree. When the algorithm starts, it

95
00:04:08,034 --> 00:04:10,233
will first call the Push_all_left function on

96
00:04:10,234 --> 00:04:13,066
the root of the tree. This will essentially

97
00:04:13,067 --> 00:04:15,366
push all the left child of the root onto the

98
00:04:15,367 --> 00:04:18,366
stack. The root will be the first one that

99
00:04:18,367 --> 00:04:21,399
will be pushed, followed by its child which is,

100
00:04:21,433 --> 00:04:26,100
which is Elia, and then finally Caryl will

101
00:04:26,101 --> 00:04:28,266
be the last one to be pushed onto the stack.

102
00:04:28,466 --> 00:04:31,766
Since the stack maintains a First in, Last out

103
00:04:31,767 --> 00:04:33,933
order, therefore the top of the stack is

104
00:04:33,934 --> 00:04:37,166
pointing to Caryl. The algorithm will then

105
00:04:37,200 --> 00:04:40,033
make a call to the Next_page function.

106
00:04:40,200 --> 00:04:42,533
This will further call next_name

107
00:04:42,534 --> 00:04:44,100
function 10 times to retrieve

108
00:04:44,101 --> 00:04:46,566
the names of 10 participants in an

109
00:04:46,567 --> 00:04:49,666
alphabetical order. As pointed out a little

110
00:04:49,667 --> 00:04:51,800
while ago, the next_name function

111
00:04:51,801 --> 00:04:55,100
do two thing, first, it will pop the top most

112
00:04:55,101 --> 00:04:58,333
element from the stack. This means that Caryl

113
00:04:58,366 --> 00:05:01,066
will be popped up. Once popped out, we will

114
00:05:01,067 --> 00:05:03,266
add it to some list that is the display list,

115
00:05:03,267 --> 00:05:07,166
so I will name it Output for now. Next, it

116
00:05:07,167 --> 00:05:09,500
will move to the right child of the popped

117
00:05:09,501 --> 00:05:12,433
element, and we'll call the Push_all_left and

118
00:05:12,434 --> 00:05:14,900
on that particular node. Since there is no

119
00:05:14,901 --> 00:05:16,766
right child, therefore nothing else will be

120
00:05:16,767 --> 00:05:19,166
pushed on to the stack. If the right child

121
00:05:19,167 --> 00:05:21,966
would have existed, then we would be pushing

122
00:05:21,967 --> 00:05:24,966
the right child itself, and all the left child

123
00:05:25,000 --> 00:05:28,300
of the right child onto the stack. The second

124
00:05:28,301 --> 00:05:30,733
called the Next_name function

125
00:05:30,734 --> 00:05:33,400
will again perform its two step operation.

126
00:05:33,401 --> 00:05:35,400
First, it will pop out the top of the stack

127
00:05:35,433 --> 00:05:38,400
element which is Elia. Next, it will move to

128
00:05:38,401 --> 00:05:40,833
the right child, and will push the right

129
00:05:40,834 --> 00:05:44,333
child itself and all of the left child of the

130
00:05:44,334 --> 00:05:47,333
right child onto the stack. Since the right

131
00:05:47,334 --> 00:05:50,333
child of the Elia is Elvira. Therefore,

132
00:05:50,334 --> 00:05:53,833
Elvira will be pushed, and since there is no

133
00:05:53,834 --> 00:05:57,366
left child of Elvira, so therefore, no

134
00:05:57,367 --> 00:06:00,366
more elements will be pushed. That new shape

135
00:06:00,367 --> 00:06:01,866
of the stack will look like this.

136
00:06:02,866 --> 00:06:05,700
Next, we will make a third call to the Next_name.

137
00:06:05,701 --> 00:06:07,466
Again the top of the stack will be popped,

138
00:06:07,467 --> 00:06:09,733
and since there is no right child, so no new

139
00:06:09,734 --> 00:06:12,000
element will be pushed, the new stack will

140
00:06:12,001 --> 00:06:14,666
only contain the root now. The fourth call

141
00:06:14,966 --> 00:06:18,566
will now pop that root first. Next, it will

142
00:06:18,567 --> 00:06:20,800
grab the right child, and will push it onto

143
00:06:20,801 --> 00:06:23,100
the stack, and moreover, it will also push all

144
00:06:23,101 --> 00:06:25,566
the left child of the right child into the stack.

145
00:06:26,100 --> 00:06:28,166
The new stack will now contain these

146
00:06:28,167 --> 00:06:31,466
elements, this process will continue. At each

147
00:06:31,467 --> 00:06:34,600
step the popped elements are added to the output

148
00:06:34,800 --> 00:06:37,200
which contains the names in alphabetical order.

149
00:06:37,800 --> 00:06:40,333
The next call will pop the Lala, and

150
00:06:40,334 --> 00:06:43,266
does not have any right child, so no

151
00:06:43,267 --> 00:06:46,100
new element will be added. The sixth call

152
00:06:46,101 --> 00:06:48,300
will pop the top element and will add the

153
00:06:48,333 --> 00:06:50,966
right child to the stack. The seventh call

154
00:06:50,967 --> 00:06:53,866
will pop the last element from the stack, also

155
00:06:53,867 --> 00:06:56,666
leaving the stack empty. This empty stack

156
00:06:56,667 --> 00:06:58,566
will indicate that there are no more elements

157
00:06:58,567 --> 00:07:00,100
in the stack, and therefore the algorithm

158
00:07:00,101 --> 00:07:02,833
should stop. Okay now that we have understood

159
00:07:02,834 --> 00:07:04,633
the problem and the solution in detail, it

160
00:07:04,634 --> 00:07:07,066
will be very easy to implement it. We will do

161
00:07:07,067 --> 00:07:08,800
the implementation in the next tutorial. So

162
00:07:08,801 --> 00:07:10,433
do come back again for covering that and

163
00:07:10,434 --> 00:07:12,600
until then happy Rust programming.

164
00:07:12,601 --> 00:07:17,966
[No Audio]