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.
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 CustomStringConformance 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
inout String, also with no argument label.
Inside the function, add a
guard let statement that unwraps
node, if it fails, simply
return out of the function.
guard let statement, call
inOrderTraversal(_:_:) on the left side of the current node by passing in
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) “.
inOrderTraversal(_:_:) passing in
result to traverse the right side of the tree.
Back inside the
- Add a variable,
text, and assign it to an empty string
inOrderTraversal(_:_:), passing in
- Change the return statement from an empty string to
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!