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.
Instructions
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 parent with to as an argument label. Both parameters are BinaryNode<T> types.
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.
Inside this 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 createsexistingLeftNodeifparent.leftChildexists. - Inside the
ifclause, calladd(_:to:), passing innodeandexistingLeftNode. - Add an
elseclause that sets theparent‘sleftChildequal tonode.
Add an 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.
Inside the else if, implement the same logic from the if clause, just using existingRightNode and rightChild in the if-let statements.