CYBER WEEK SALE: Get 50% off your Pro annual membership using code [CYBER23](https://www.codecademy.com/checkout?periods=year&plan_id=proGoldAnnualV2&discountCode=CYBER23)


Binary Search Trees: Swift

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


Review

With our private `add(_:to:)` function complete, it is time to implement our public-facing `add(_:)` method. Users don’t need to be able to add a value to specific subtrees in our structure, actually, if we allowed them to do this, it might break the rules of our BST.

The public-facing function will also handle the case of adding the first value to our tree, the root. We don’t have an initializer for the `BinarySearchTree` class because the instance variable is optional. This is common when you want a user to be able to create an instance of your class without having to know any of the values they want to add yet.

Our public function will also simply allow the user to add any value that is the same type of the tree using generics to enforce the type conformance.


Public add Method

Our implementation of a searching function will provide the user with a boolean value as to whether the value is in the tree or not. Since it provides the user with this type of answer, we will call the function `contains(_:)`. Similar to how the add function we created was implemented, we will have a private variation, `contains(_:startingAt:)` that will do the heavy lifting (recursion) behind the scenes.

Since this private function will use a standard recursive algorithm, let’s talk about our base case:
- When the node we are searching is nil, that is we’ve searched all the way to the end of a tree and can’t find the element, we will return false.
- If we reach a node that is not nil and its value is neither less than or greater than the value, it must equal the value and we return true.

If we don’t reach a base case, call the function on the left child if the value is less than the parent or the right child if it is greater than the parent.

The public function will take a value from the user and simply call the private function beginning at the root of the tree.


Hunting For Items

Now that we have a insertion and searching in our binary search tree, the next functionality we will add is data removal. As you can imagine, removing data from a BST is not just as simple as deleting a reference to a node, we need to do some background work.

In pseudocode, our algorithm runs like this:
```
1. Check if the node passed into the function exists, if not, return nil

2. Check the value we are looking for against the current node’s data
   - Recurse down either the left or right child depending on if value is less than or greater than the current node

3. When you value equals the current node’s data, check if it has two children, if not, that node is replaced with it’s only child

4. If it has two children, find the smallest value on the right side and replace the current node’s value with that and setting the smallest right hand node to nil. The smallest value on the right hand side is guaranteed to be larger than the value on the left so when we replace it, it keeps the rules of the BST. This value is also guaranteed to be a leaf node (no children), so we can set it to nil once we have swapped its value into the current node we are trying to remove.
```

We will build the helper function to find the smallest value on the right hand side of a tree. The function can be used to find the smallest value in in the whole tree, but we only need it for this particular function.


Finding the Smallest Value

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](https://static-assets.codecademy.com/Paths/ios-skill-path/PassingTheTechnicalInterview/treeImage.png)
*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.

In-Order Traversal and Printing the Tree

A _binary search tree_ (BST) is a specialized form of a standard binary tree. We have already built a binary tree inside of our heaps class so the structure will feel familiar as we implement our changes to make a true BST. Binary search trees are a very efficient storage system for data storage, lookup, and removal with the time complexity of all operations directly proportional to the height of the tree. Since a binary tree can have at most two children, we eliminate half the remaining tree with each iteration of a function or in Big O notation, O(log n), where n is the number of nodes in the tree. This is true as long as the tree is reasonably balanced. If addition into the tree is performed on sorted data, it will result in a tree that always only uses either the left or right branch, leading the height of the tree to be as large as the data set and bringing the time complexity to O(n) time.

The basic rules of a binary search tree are:
- The left child and its subtree contain values less than the parent node’s values
- The right child and its subtree contain values greater than the parent node’s values
- Each left and right subtree is in itself an implementation of a BST

Throughout this implementation, we will create methods to add, remove, search, and print a BST as well as retrieve the minimum value in our tree.

At the conclusion of our Tree lesson, we provided a generic implementation of a Tree to start you down the path of creating [generic data structures](https://docs.swift.org/swift-book/LanguageGuide/Generics.html). In this lesson, we will be creating a generic BST throughout and teaching you how to add additional restrictions to your generics to ensure your code isn’t broken by someone trying to pass in custom objects.

Introduction to BSTs

We’ve solved step 4 of our pseudocode algorithm, let’s review the code again to finish implementing our remove functions.

```
1. Check if the node passed into the function exists, if not, return nil
2. Check the value we are looking for against the current node’s data
   - Recurse down either the left or right child depending on if the value is less than or greater than the current node
3. When your value equals the current node’s data, check if it has two children, if not, that node is replaced with its only child
4. If it has two children, find the smallest value on the right side and replace the current node’s value with that, and setting the smallest right-hand node to nil.
```

Similar to our previous design patterns, this logic will be contained in a private `remove` method and the user will have a public `remove` method that simply accepts a value to remove from the tree.



Removing Items from a BST

When we add elements to a binary search tree we have to ensure that we are following the rules of the data structure:
- All values less than a parent’s value are stored on the left side of the tree
- All values greater than a parent’s value are stored on the right side of the tree
- All subtrees also follow the basic rules of a binary search tree

We will have two functions, a private function that uses recursion to traverse the tree until we’ve reached the appropriate insertion location, and a public function that the user will use to insert a generic value into the tree.

In our tree we will not allow duplicate values, making our BST exclusive. We will not search for a value in the tree before we attempt to add it, instead, if a duplicate value is added, it will enter the regular add function and when the insertion reaches a point where the value is neither less than or greater than (that would mean it is equal), it simply does nothing. The main point of doing it like this is to increase performance. If we were working through a huge dataset, having to search and insert adds unnecessary time complexity.

