Understanding Depth & Breadth-First Search in Swift

With each node possibly having a root, left and right descendants, we must apply an alternate technique that takes into account the depth of the structure we plan to explore:Here’s an example of a balanced binary search tree (BST)..The number each node displays represents the path our depth-first search (DFS) will take..As mentioned, this technique takes into account the depth of the structure by exploring all values on the left side of the model before proceeding to the right..Applied correctly, a DFS traversal will output the values shown in sequential order..Assuming our BST data structure is recursive, the code can be expressed as follows://generic node to be used with binary search trees (BST’s)class BSNode<T>{ var key: T?.var left: BSNode?.var right: BSNode?.var height: Int init() { self.height = -1 }//regular dfs traversalfunc DFSTraverse() { //trivial condition guard let key = self.key else { print(“no key provided..”) return } //process the left side if self.left != nil { left?.DFSTraverse() } print(“now visiting node: (key)”) //process the right side if self.right != nil { right?.DFSTraverse() } }}Depth-First Search is one of the few exceptions where it makes good sense to apply a recursive algorithm..Since the model we are exploring also has recursive properties, we can acquire additional functionality (for free) by utilizing the call stack.BREADTH-FIRST SEARCHBreadth-First Search (BFS) provides an alternate technique for traversing data structures..More detailed than DFS, Breadth-First Search works by visiting our neighbor before visiting our neighbor’s neighbor..As such, BFS is designed to traverse structures based on discovery..This technique makes it ideal for traversing open-ended models like a Graph:Starting the BFS process.. More details

Leave a Reply