# Traversals

Throughout this series we've explored building various data structures such as binary search trees and graphs. Once established, these objects work like a database - managing data in a structured format. Like a database, their contents can also be explored though a process called traversal. In this essay, we'll review traversing data structures and will examine the popular techniques of Depth-First and Breadth-First Search.

Traversals are based on "visiting" each node in a data structure. In practical terms, traversals can be seen through activities like network administration. For example, administrators will often deploy software updates to networked computers as a single task. To see how traversal works, let's introduce the process of Depth-First Search (DFS). This methodology is commonly applied to tree-shaped structures. As illustrated, our goal will be to explore the left side of the model, visit the root node, then visit the right side. Using a binary search tree, we can see the path our traversal will take:

The yellow nodes represent the first and last nodes in the traversal. The algorithm requires little code, but introduces some interesting concepts.

//depth-first in-order traversal func processAVLDepthTraversal() { //check for a nil condition if (self.key == nil) { println("no key provided..") return } //process the left side if (self.left != nil) { left?.processAVLDepthTraversal() } println("key is \(self.key!) visited..") //process the right side if (self.right != nil) { right?.processAVLDepthTraversal() } } //end function

At first glance, we see the algorithm makes use of recursion. With recursion, each `AVLTree`

node (e.g. self), contains a `key`

, as well as pointer references to its `left`

and `right`

nodes. For each side, (e.g., left & right) the base case consists of a straightforward check for `nil`

. This process allows us to traverse the entire structure from the bottom-up. When applied, the algorithm traverses the structure in the following order:

3, 5, 6, 8, 9, 10, 12

### Breadth-First Search

Breadth-First Search (BFS) is another technique used for traversing data structures. This algorithm is designed for open-ended data models and is typically used with graphs.

Our BFS algorithm combines techniques previously introduced including stacks and queues, generics and Dijkstra’s shortest path. With BFS, our goal is to visit all neighbors before visiting our neighbor’s, “neighbor”. Unlike Depth-First Search, the process is based on random discovery.

We've chosen `vertex`

A as the starting point. Unlike Dijkstra, BFS has no concept of a destination or frontier. The algorithm is complete when all nodes have been visited. As a result, the starting point could have been any node in our graph.

*Vertex A is marked as visited once its neighbors have been added to the queue.*

As discussed, BFS works by exploring neighboring vertices. Since our data structure is an undirected graph, we need to ensure each node is visited only once. As a result, vertices are processed using a generic queue.

//breadth-first traversal func traverseGraphBFS(startingv: Vertex) { //establish a new queue var graphQueue: Queue<Vertex> = Queue<Vertex>() //queue a starting vertex graphQueue.enQueue(startingv) while(!graphQueue.isEmpty()) { //traverse the next queued vertex var vitem = graphQueue.deQueue() as Vertex! //add unvisited vertices to the queue for e in vitem.neighbors { if e.neighbor.visited == false { println("adding vertex: \(e.neighbor.key!)") graphQueue.enQueue(e.neighbor) } } vitem.visited = true println("traversed vertex: \(vitem.key!)..") } //end while println("graph traversal complete..") } //end function

The process starts by adding a single `vertex`

to the `queue`

. As nodes are dequeued, their neighbors are also added (to the queue). The process completes when all `vertices`

are visited. To ensure nodes are not visited more than once, each `vertex`

is marked with a boolean flag.

*Like this series? Subscribe to the newsletter and receive a free guide on iOS interview tips.*