[No Audio]
Consider a business which has a software for
conducting online meetings of its employees.
The company wants to keep track and display
the list of participants attending the
meeting using a suitable data structure.
The company wants the names of the attendees in a
meeting to be displayed in an alphabetical
order. The attendees can join or leave a
meeting at random, so the underlying data
structure should allow for easy updation accordingly.
After analyzing the problem, the
designer team has agreed that the name of the
attendees should be stored using a binary
search tree. Once the names are stored, the
company is further interested in a special
mode of display called gallery mode.
This display will allow the names of the
participants to be shown in paginated form,
that is divided into pages that can be
scrolled down. In this scenario, we will
assume that only 10 participant can be shown
on one page. Our job is to use the binary
search tree containing the names of the
participants and implement the pagination.
Whenever our function is called the names
of the next 10 participants should be
returned in an alphabetical order. Let us
further elaborate the problem using
PowerPoint slides for a better understanding.
Consider this to be the binary search tree
corresponding to the participants. The
details of the binary search tree are already
covered in the same section, so we will not
be digging deep into the details. We will
however repeat the main characteristic or
property, which is that for each node, the
left subtree of that node will contains all
the values that are lesser than the value of
the node itself. And the right subtree of the
node will contain nodes whose values are
greater than the value of the node. Please
note that, in this case, the values are
characters and not numbers. In order to
compare two values, we will use their
alphabetical order to determine whether one
value is greater than the other or lesser
than the other. Generally speaking, an
alphabet which comes first is lesser than the
alphabet which comes later. If the first
letters of the names are the same, then we
will compare based on the second letters, and
so on. The function for the pagination will
take this binary search tree as an input, and
will produce the first 10 names from the tree
as an output in an alphabetical order.
In this case, it will produce this list of
names. The second call to the function will
produce the remaining names. Please note that
since in binary search tree the values are
stored in an effective order, therefore,
retrieving the values in an alphabetical
order will be easy. We will see this in a
while. In summary, we need to implement a
pagination or display function, which will
display the values of the first 10
participants retrieved from the binary search
tree. Let us now explain our approach to
solving this problem. Our solution will
contain three key functions namely, Push_all_left,
Next_name, and Next_page. The Push_all_left
when called for a certain node, will push
all the left nodes of that node in a stack.
This function will only terminate when there
are no more left nodes to push onto the stack.
The Next_name function will return the
next name in alphabetical order from the
tree. It will be called 10 times since we
since we want to retrieve 10 names per page.
More specifically, it will do two things.
Firstly, it will pop or remove the top
element or node from the stack, and then it
will call the Push_all_left on the right
child of the removed element from the stack.
This means that it will push the right child,
and all the leftmost child of the right child
onto the stack. Finally, the Next_page
function will call the Next_name function 10
times to retrieve the required names from the
BST or binary search tree. All this may not
be very clear for now, so let us dive a bit
deep and see the solution in visual form.
Consider this to be the input BST or binary
search tree. When the algorithm starts, it
will first call the Push_all_left function on
the root of the tree. This will essentially
push all the left child of the root onto the
stack. The root will be the first one that
will be pushed, followed by its child which is,
which is Elia, and then finally Caryl will
be the last one to be pushed onto the stack.
Since the stack maintains a First in, Last out
order, therefore the top of the stack is
pointing to Caryl. The algorithm will then
make a call to the Next_page function.
This will further call next_name
function 10 times to retrieve
the names of 10 participants in an
alphabetical order. As pointed out a little
while ago, the next_name function
do two thing, first, it will pop the top most
element from the stack. This means that Caryl
will be popped up. Once popped out, we will
add it to some list that is the display list,
so I will name it Output for now. Next, it
will move to the right child of the popped
element, and we'll call the Push_all_left and
on that particular node. Since there is no
right child, therefore nothing else will be
pushed on to the stack. If the right child
would have existed, then we would be pushing
the right child itself, and all the left child
of the right child onto the stack. The second
called the Next_name function
will again perform its two step operation.
First, it will pop out the top of the stack
element which is Elia. Next, it will move to
the right child, and will push the right
child itself and all of the left child of the
right child onto the stack. Since the right
child of the Elia is Elvira. Therefore,
Elvira will be pushed, and since there is no
left child of Elvira, so therefore, no
more elements will be pushed. That new shape
of the stack will look like this.
Next, we will make a third call to the Next_name.
Again the top of the stack will be popped,
and since there is no right child, so no new
element will be pushed, the new stack will
only contain the root now. The fourth call
will now pop that root first. Next, it will
grab the right child, and will push it onto
the stack, and moreover, it will also push all
the left child of the right child into the stack.
The new stack will now contain these
elements, this process will continue. At each
step the popped elements are added to the output
which contains the names in alphabetical order.
The next call will pop the Lala, and
does not have any right child, so no
new element will be added. The sixth call
will pop the top element and will add the
right child to the stack. The seventh call
will pop the last element from the stack, also
leaving the stack empty. This empty stack
will indicate that there are no more elements
in the stack, and therefore the algorithm
should stop. Okay now that we have understood
the problem and the solution in detail, it
will be very easy to implement it. We will do
the implementation in the next tutorial. So
do come back again for covering that and
until then happy Rust programming.
[No Audio]