Code Challenge: Traversing Data Structures in Swift

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


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)

let sequence : 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: 



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
        while !bsQueue.isEmpty() {
            //traverse the next queued node
            guard let bitem = bsQueue.deQueue() else {
            print("now traversing item: \(bitem.key!)")
            //add decendants to the queue
            if let left = bitem.left {
            if let right = bitem.right {

        } //end while
        print(bfs traversal complete..")

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