Congratulations on building a binary search tree!
When implementing a BST in your own code, here are a few things to remember:
- In a BST, the left child is less than the parent and the right child is greater than the parent.
- Each subtree (parent/left child/right child) is a small BST and follows the same rules.
- On average, insertion, retrieval, and deletion all run in O(log n) time complexity
- Trees can be traversed in many ways, in order traversal will visit nodes in their least to greatest order
- Our generic implementation allows for many data types to be stored in our BST
The code in the workspace demonstrates the flexibility of our generic
BinarySearchTree. There are two instances, an
Int tree, and a
String tree. Both are built from the same
Take some time to call some of the functions you’ve built on the trees,
contains(_:). Be sure to also print the tree so you can see how it looks in each form. We’ve added some function calls of our own too to demonstrate some of the capabilities. When you’re ready to continue, click on the “Up Next” button.