Log in from a computer to take this course

You'll need to log in from a computer to start Introduction to Non-linear Data Structures in Swift. But you can practice or keep up your coding streak with the Codecademy Go app. Download the app to get started.

apple storegoogle store
Learn

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

1.

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.

2.

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.

3.

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-let statement that creates existingLeftNode if parent.leftChild exists.
  • Inside the if clause, call add(_:to:), passing in node and existingLeftNode.
  • Add an else clause that sets the parent‘s leftChild equal to node.
4.

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.

5.

Inside the else if, implement the same logic from the if clause, just using existingRightNode and rightChild in the if-let statements.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?