With the core functionality taken care of, we can focus on some of the aesthetics of our binary search tree. We are going to build in the feature that allows the tree to be printed in order, from least to greatest.

There are three basic ways to traverse a tree, pre-order, post-order, and in-order. Looking at the image below, the red circles represent pre-order, blue circles represent post-order, and the green circles represent an in-order traversal.

Tree image Source:https://en.wikipedia.org/wiki/Tree_traversal

We will implement an in-order traversal that goes to the farthest left node first, then goes back to its parent, before traversing the right child and finding the least values on the left side before moving on with the traversal.



To get started, add the CustomStringConvertible protocol to our BinarySearchTree class, this goes directly after the closing of the generic angle brackets. You should see a compile-time error because the class doesn’t conform to the protocol yet. We’ll fix that in the next step.


BinarySearchTree needs a description to conform to CustomStringConvertible. At the bottom of the class, add a new computed variable, description of type String. Inside the curly brackets, return an empty string.


Create a new function, inOrderTraversal(_:_:), that has two parameters:

  • node, an optional BinaryNode<T> with no argument label
  • result, an inout String, also with no argument label.

Inside the function, add a guard let statement that unwraps node as node, if it fails, simply return out of the function.


After the guard let statement, call inOrderTraversal(_:_:) on the left side of the current node by passing in node.leftChild and result. When using inout variables, you need to add & before the variable name.


After the recursive function call on the left side of the tree, set result equal to itself plus “(node.data.description) “.


Finally, call inOrderTraversal(_:_:) passing in node.rightChild and result to traverse the right side of the tree.


Back inside the description property:

  • Add a variable, text, and assign it to an empty string
  • Call inOrderTraversal(_:_:), passing in root, andtext`
  • Change the return statement from an empty string to text

Great work! You’ll see one example of a tree at the bottom of the file. Uncomment it and see what the new description property in action!

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?