# Traversing Data Structures in Swift

Recently I had the chance to help a student in the iOS Interview Program prepare for a significant technical interview at a company most individuals would recognize. Overall, my courses blend a mix of code challenges and live whiteboarding sessions that test one’s ability to implement syntax, design patterns and algorithms in Swift.

### The Challenge

Occasionally I hear back from folks about their interview experiences. Sometimes, a certain type of question takes developers by surprise. If you recognize the challenge - fabulous! For the rest of us, here's the summary:

// Given the following tree: // 1 // 2 3 // 4 5 7 // 8 9 //implemented by this class: class`BSNode`

<T> { var key: T? var left:`BSNode`

? var right:`BSNode`

? var height:`Int`

init() { self.`height`

= -1 } } // use the below function to get the following output: // expected output: // 1 // 2 3 // 4 5 7 // 8 9 // results: 1 2 3 4 5 7 8 9

### THE ANALYSIS

What's interesting about the challenge is the number of things it measures. This includes one's general technical background, understanding of Swift, as well as computer science principles. As a new or experienced iOS developer, we are accustomed to working with native Swift types like **Array's** & Dictionaries. As such, it's easy to iterate through these list of elements. We can use fast enumeration to **traverse** an Array in **linear time - O(n)**:

letsequence:`Array`

<Int> = [1, 2, 3, 4, 5, 6, 7] //linear time - O(n)`func`

linearSearch(for value: Int, list:`Array`

<Int>) ->`Bool`

{ //traverse through the range of values`for`

number`in`

list { if number == value {`return`

true } }`return`

false }

For our challenge, the difficulty is that a tree-based structure isn't one-dimensional. As a result, the technique of fast enumeration can't be applied. To solve the question we need to come up with an alternate method to account for the values below the **root node** (e.g., 1). This idea can be thought of as the tree's **depth**. Consider this more detailed view:

### THE IMPLEMENTATION

To satisfy our criteria, we can apply the technique of Breadth-First Search** **(BFS). Unlike typical interview questions that involve counting, sorting or string manipulation, BFS has a specific purpose which would be quite difficult to replicate otherwise. When it comes to traversals, the advantage is that BFS is based on **discovery**. This procedure creates flexibility when traversing complex, open-ended systems like Graphs and Trees. Consider the following:

//breadth-first search - tree traversal`func`

BFSTraverse() -> () { //establish a queue let bsQueue = Queue<`BSNode`

<T>() //queue a starting node bsQueue.enQueue(`self`

)`while`

!bsQueue.isEmpty() { //traverse the next queued node`guard`

let bitem = bsQueue.deQueue()`else`

{break}`if`

let left = bitem.left { bsQueue.`enQueue`

(left) }`if`

let right = bitem.right { bsQueue.`enQueue`

(right) } } //end while

Shown above, the code is implemented through the use of a **Queue**. Scheduling items with a Queue is ideal because it ensures objects get traversed in a First-In/First-Out manner. It's this process that allows us to print the elements in our challenge in sequential order. Also, since the model is based on discovery, the algorithm continues to search for new items until the **Queue** is empty. In this example, the BFS algorithm makes use of a custom **Queue**. However, similar queueing functionality could be achieved through the use of an **Array**.