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.
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.
Instructions
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 optionalBinaryNode<T>with no argument labelresult, aninout 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 inroot, 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!