Learn

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 removeChild(_:) and printFrom(_:_:) methods. The recursive steps of each of those methods follow the same logic:

  1. Grab a node and do something (like print it)
  2. 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:

  1. Post-order, in which we begin with children and visit parents sequentially (not quite as simple as this)
  2. 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.

Instructions

1.

Inside the 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.

2.

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: "\(startAtNode) "

3.

Next, create a for-in loop that iterates through each child in startingAtNode.children and recursively calls depthFirstTraversal() on each child.

4.

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.

5.

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!

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?