What good is a tree if we can’t climb it? In general, there are two ways to climb a tree:
- Depth-First Traversal: climbing from the root and following each branch down to its leaves
- Breadth-First Traversal: climbing all the branches on the same level (depth) before moving to the next level.
Actually, we’ve already been doing Depth First Traversal in both the
printFrom(_:_:) methods. The recursive steps of each of those methods follow the same logic:
- Grab a node and do something (like print it)
- If that node has children, call this method for each child and continue until you reach a level with no children
There are several different ways to implement a depth-first algorithm; we will tackle a “pre-order” traversal. This method is great at providing a topographically view of our tree so we can visualize the structure. The two other methods are:
- Post-order, in which we begin with children and visit parents sequentially (not quite as simple as this)
- In-order, which we will implement in our binary search tree in an upcoming lesson, and returns the nodes in sequential order (assuming we have defined what one node being greater than the other node means).
We will create a method,
depthFirstTraversal(), that will move through the tree in this way. We will start by simply printing the data of each node so you visualize the traversal. However, in the end, we can modify the code to have it perform any task you want on the nodes.
Tree class and underneath the
printFrom() method, create a new method,
depthFirstTraversal() that takes one parameter,
startingAtNode of type
TreeNode, leave the method body empty.
Inside the function, use the standard
Swift.print(_:separator:terminator:) function to print the
startingAtNode but change the
terminator argument to an empty string instead of the default which is a new line.
You should print the
startingAtNode using string interpolation followed by a space:
Next, create a
for-in loop that iterates through each
startingAtNode.children and recursively calls
depthFirstTraversal() on each
Uncomment the line of code that calls
depthFirstTraversal() on the
familyTree. It’s a little hard to follow when printed like this, but you should notice the flow of the recursion.
Uncomment the last two lines of code and match up your depth-first printing to the standard tree printing, they are in the same order!