Help understanding the recursion for Depth-first traversal

📚 Official Books Data Structures & Algorithms in Swift
1

Can anyone help me understand what exactly is going on through the Depth-first traversal method?

    public func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self)
        
        children.forEach {
            $0.forEachDepthFirst(visit: visit)
        }
    }
}
2

@jomoka Can you please help with this when you get a chance? Thank you - much appreciated! :]

3

@anothershitdev yea for sure!

So keep in mind that:
Depth-first traversal keeps going down one branch till it reaches a leaf node, hence depth.
Breadth-first traversal goes down level by level, meaning it traverses all it’s child nodes before it goes down another level, hence breadth.

This depth-first traversal function is a little tricky. forEachDepthFirst takes in a closure called visit which returns a TreeNode and returns nothing.

 public func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self) // 1
        
        children.forEach { // 2
            $0.forEachDepthFirst(visit: visit)
        }
    }
}

The method does the following:

  1. Executes the visit closure. This basically just executes any function that gets passed into forEachDepthFirst. For example printing the current node we are on.
  2. For every child node this will recursively continue to go down one branch of a tree till it reaches a leaf node. Once it reaches a leaf node, it backtracks and continues down another branch!

If you look at the example code as shown below:

example(of: "depth-first traversal") {
  let tree = makeBeverageTree() // 1
  tree.forEachDepthFirst { print($0.value) } // 2
}
  1. You first create a binary tree of beverages.
  2. You call the forEachDepthFirst which passes in a closure. A closure is just a function or method. In this case the function just prints out every node during the depth-first traversal. $0 is just a short hand argument, but it’s type is just TreeNode.

Hopefully this helps, let me know if you have any other questions!