Code Challenge: Traversing Data Structures in Swift / by Wayne Bishop

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)


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: 

 
extras-bfs-traversal.png
 

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
            }
            
            print("now traversing item: \(bitem.key!)")
            
            //add decendants to the queue
            if let left = bitem.left {
                bsQueue.enQueue(left)
            }
            
            if let right = bitem.right {
                bsQueue.enQueue(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