LeetCode's challenge #102 asks us to traverse a Binary Search Tree in level order. Level order traversal is the key to solve a multitude of tech challenges and comes up in many different varieties within numerous questions on LeetCode.

The idea is: We enqueue the root of the tree into a queue. Within a while loop, we dequeue the root and enqueue each child while maintaining the current level.  

Our disadvantage using Swift is that the standard library doesn't come with a native queue implementation. If we were to use an array, we'd get from a linear to a quadratic time complexity. This is because removing the first element of an array is in itself a linear operation because of the need to shift all indices.

In other words: While the loop we need to use to get all nodes from the BST is a linear operation O(n), shifting all indices is also a linear operation O(n) and combined is therefore O(n) * O(n) ->  O(n * n) -> O(n^2).

QueueStack to the rescue

The advantage of our QueueStack implementation is that all operations are constant in time. We're appending elements to the end of the queue and reversing the enqueueStack into the dequeueStack and popping the last element of it.

The typealias NodeAtLevel makes life easier as we don't have to spell out (node: TreeNode, level: Int) over and over again.

Level Order Traversal

1) The first step is to check that the root node actually exists. Without a root node, there is no BST and we can safely return an empty array.

2) We are initiating a new QueueStack. As you learned, the QueueStack is data structure that wraps two arrays. An array to enqueue and one array to dequeue elements into/from the queue.

3) Since the expected return type is an array, we are enqueueing the root node at level 0. Because of the guard statement on top, we know that the root exists for sure at this point in the function.

4) We create an empty array that we will fill with the values at each level. In a best case scenario, we would initialize the array with the expected count. However, at this point, the height of the tree is unknown.

5) While the queue still contains elements, we will run this while loop.

6) First within the loop, we want to dequeue the top element of the queue. Since our typealias defined a tuple of (node: TreeNode, level: Int), we can access the dequeued element as let (node, level).

7) Next, we need to check if we are just starting out at the current level, or if we have already processed values at the current level.

8) If we have nodes at the level (index), we are able to safely append the element to the existing array of values.

9) If this is the first node/value we're processing at the current level, we just append the value, wrapped into an array, at the current level.

10/11/12) Lastly, we check if we have left/right children and we add those to the queue by incrementing the level by 1.