We need to develop a display structure for the list of participants attending a MS Teams meeting. As you know, the names of attendees in a MS Teams 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, MS Team 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.
- constructor: This function 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
push_all()with the root of BST as a parameter. push_all(): 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 becomesNone. 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.next_name(): This function returns the next element in the stack at any moment. The stack is popped to find the next smallest element. Then, it is populated again by calling thepush_all()function on the popped element’s right child, and the popped element is returned. We do this because the function returns the smallest element of the BST. Finally, it simulates recursion by moving one step forward towards the next smallest element, which is inside the right subtree of the smallest element.has_next(): This function lets us know if the next element exists in the stack. This is done by checking if the stack is empty or not. We use this helper function to avoid exceptions.next_page(): This is the function that implements pagination by returning a maximum of ten participants at a time. Inside this function, we will call thenext_name()function ten times and populate the resulting array. Before calling thenext_name()function, we will call thehas_next()function to check if the stack is empty. If the stack is empty, we will break the loop and return the result.
The following illustration demonstrates all the algorithm’s steps:
The implementation of this algorithm is given below:
Time complexity
The time complexity analysis of this feature is not straightforward. If we look at each function (except has_next()) individually, they have O(n) complexity for the worst-case. However, in actuality, there is no possible case where all of these will be O(n) at the same time. The push_all() function is the most expensive operation. It is O(n) for the worst-case. However, we only call push_all() for the nodes that have the right child. Also, if we end up calling it, it will not process n nodes each time. Even if we have a fully skewed tree, push_all() will be O(n) only once. For later calls, it will be O(1). Therefore, the amortized time complexity for this function will still be O(1). As next_name() and next_page() also, depend upon, push_all()their complexity will also be O(1).
Space complexity
Similarly, the space complexity will be O(n) for the complete algorithm because we are keeping a custom stack.
If you like the content please follow me here @medium and at LinkedIn
