Feature #1: Display Meeting Lobby

Description

For the first feature of the Zoom application, we need to develop a display structure for the list of participants attending a Zoom meeting. As you know, the names of attendees in a Zoom meeting are displayed in alphabetical order. However, attendees can join or leave a meeting at random, so the order has to be updated continuously. To tackle this issue, Zoom has decided to store the names of attendees in a binary search tree (BST). Additionally, we are specifically working on a meeting’s “Gallery Mode” display., where the participants’ names/videos are paginated (divided into pages that can be scrolled). In this scenario, we will assume that only ten participants can be shown on one page.

Our task is to use the binary search tree containing the names of participants and implement the pagination. Whenever our function is called, the names of the next ten participants should be returned in alphabetical order. Consider the following binary search tree, which contains the names of meeting attendees:

Assume that the above-mentioned binary search tree is provided as our feature’s input. The first time the function is called, it should return the following list: ["Albert", "Antoinette", "Anya", "Caryl", "Cassie", "Charity", "Cherlyn", "Elia", "Elvira", "Iliana"]. After the second call, it should return [ "Jeanette", "Kandice", "Lala", "Latasha", "Lyn"]. All calls after that should return [].

Solution

We can implement this feature with the help of the in-order traversal algorithm. We will simulate an in-order traversal using a custom stack and an iterative, rather than recursive, approach. In the solution below, some helper functions are also implemented to make it modular and reusable. Let’s take a close look at the implementation of each function in the DisplayLobby class.

• DisplayLobby(): The constructor will take the root of the BST as input and create a stack. The values of the tree will populate the stack by calling the helper function pushAll() with the root of BST as a parameter.

• pushAll(): This function will take a node as input. We will start traversing the tree from the node provided. The value of the current node will be pushed inside the stack, and we will jump to the left child of the current node and continue the process until the current node becomes nullptr. This way, we will be adding the leftmost branch of the tree (rooted at the input node) into the stack. For the input node, the next smallest element in the tree will always be the leftmost element in the tree. So, for a given root node, we will follow the leftmost branch until we reach a node that doesn’t have a left child. This node will be the next smallest element.

• nextName(): This function returns the next element in stack at any moment. The stack is popped to find the next smallest element. Then, it is populated again ...