How to change this method w/o using recursion?

📚 Official Books Data Structures & Algorithms in Swift
1

Hi Kelvin and Vincent, in chapter 6 of Trees, can you please rewrite this method without using recursion? Thanks!

“extension TreeNode {
public func forEachDepthFirst(visit: (TreeNode) → Void) {
visit(self)
children.forEach {
$0.forEachDepthFirst(visit: visit)
}
}
}”

Excerpt From: By Kelvin Lau. “Data Structures & Algorithms in Swift.” iBooks.

2

Hi @mike,
I am sure that Kelvin and Vincent will chime in on this.

I had some thoughts on this, first being that why would you want to not use recursion? The alternative would involve you keeping track of which node you are traversing and you have already traversed. If you still want to do that, you might want to create a stack that keeps track of the node that you are visiting. So it pushes that value onto the stack when it starts to traverse the node and pops on completion.

will try to write some pseudo or code when I get some time, if you do not get the authors response,

cheers,

Jayant

3

@jayantvarma thanks for replying. Although I understand basics of recursion, I do not understand the code in the method, especially the visit(self) and visit: visit part. It seems that there is nowhere else defining how to implement the closure (TreeNode) → Void). If you could explain the func line by line, that would be very helpful.

Thanks again for your time and have a great day!

4

Hi @mike,
that helps - because this is the actual question that you wanted to ask. Explaining this is easy,

The code that you refer to on page 74 and 75 make sense in context and together.
The function is called forEachDepthFirst and it takes a parameter of type TreeNode and returns nothing, this in other words is a closure or as one would call a function. This parameter is named and called value. (for more details look at named parameters in swift)

So the first thing it does is call this closure with the treenode we are traversing using visit(self)

then we traverse through each of the children using a children.forEach { which is the equivalent of a for node in children { the function is called recusively and the closure that is stored in the value of visit is called again using $0.forEachDepthFirst(visit: visit)

Then when this is called using the code below, it could make better sense,

    let tree = makeBeverageTree()
    tree.forEachDepthFirst(visit: { print($0.value) })

Hope that helped you to understand this, the closure is listed on page 75, and could be the reason why it was confusing at first.

cheers,

Jayant

5

@jayantvarma Hi Jayant,

Thanks for your quick response. Yes, this is my actual question and thanks for your perfect answer. Now I understand and no need for another method without recursion.

Cheers,
mike

6

hi @mike, glad it helped you.

cheers,

Jayant