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

```
struct Queue {
typealias NodeAtLevel = (node: TreeNode, level: Int)
private var enqueueStack: [NodeAtLevel] = []
private var dequeueStack: [NodeAtLevel] = []
public var isEmpty: Bool {
return enqueueStack.isEmpty && dequeueStack.isEmpty
}
public mutating func enqueue(_ node: TreeNode, at level: Int) {
enqueueStack.append((node, level))
}
public mutating func dequeue() -> NodeAtLevel? {
if dequeueStack.isEmpty {
dequeueStack = enqueueStack.reversed()
enqueueStack.removeAll()
}
return dequeueStack.popLast()
}
}
```

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

```
func levelOrder(_ root: TreeNode?) -> [[Int]] {
// 1
guard let root = root else {
return []
}
// 2
var queue = Queue()
// 3
queue.enqueue(root, at: 0)
// 4
var output: [[Int]] = []
// 5
while !queue.isEmpty {
// 6
let (node, level) = queue.dequeue()!
// 7
if level < output.count {
// 8
output[level].append(node.val)
} else {
// 9
output.append([node.val])
}
// 10
if let left = node.left {
// 11
queue.enqueue(left, at: level + 1)
}
// 12
if let right = node.right {
queue.enqueue(right, at: level + 1)
}
}
return output
}
```

**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

, we can access the dequeued element as `(node: TreeNode, level: Int)`

`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**.