Code Challenge: Traversing Data Structures in Swift

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:The ImplementationTo 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.. More details

Leave a Reply