# LeetCode #102 — Binary Tree Level Order Traversal

**Find more useful articles at ****www.davidseek.com**

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

**Find more useful articles at ****www.davidseek.com**