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.
Add a new private function,
add(_:to:) under the multiline comment for the function. It should have two parameters,
node with no argument label and
to as an argument label. Both parameters are
Leave the function body empty.
Inside the function, add an
if statement that checks if the
node’s value is less than the
parent’s value, leave the statement body empty for now.
if statement, we will check if the tree has a left child, if it does, we will call
add(_:to:) again on that node, if it doesn’t have a left child, we add the new node here. To implement this:
- Create an
if-letstatement that creates
- Inside the
add(_:to:), passing in
- Add an
elseclause that sets the
else if clause to the original
if statement, it will check if the
node’s value is greater than the
parent’s value, you can leave the body empty for now.
else if, implement the same logic from the
if clause, just using
rightChild in the