Learn

Logically, after creating the ability to add children to your tree, the next step would be to write code that also removes children. To accomplish this functionality, we’ll need to take a few necessary steps, the first being how to determine equality among TreeNodes. It does us no good to ask our program to remove a specific TreeNode if we have no way of identifying that node within our tree.

Swift provides a protocol for just this purpose, Equatable. A type that conforms to the Equatable protocol can be compared for equality using the “==” or “!=” operators.

These types of operators are known as infix operators, as they typically sit between two targets. You use many of them all the time (+, -, *, /) and most can be overloaded, meaning we can define specific functionality for them in our classes. For example, we could define the + function in our TreeNode class to “add” one TreeNode’s data String to another. It might look something like:

extension TreeNode { static func + (left: TreeNode, right: TreeNode) -> String { return left.data + “ “ + right.data } }

Now, if we were to create two TreeNodes, we could “add” them and print the result.

var branch1 = TreeNode(data: “I’m node 1 ”) var branch2 = TreeNode(data: “and I’m node 2.”) print(branch1 + branch2) // Prints: “I’m node 1 and I’m node 2.”

In order for our TreeNode to become Equatable, we need to define what equality means to us:

  • Both TreeNodes have the same data value
  • Both TreeNodes have the same children

This is truly tree-specific and different situations will call for different definitions of equality. Your end product will be a family tree, and it is possible for a family to have two people named the same. By also checking to make sure that the children are equal, we can remove the right person from the tree (most of the time).

Instructions

1.

In order to use the Equatable protocol, create an extension of the TreeNode class just below the final curly brace of the TreeNode class and add the Equatable protocol to the extension. Leave the extension empty for now.

If it has been a while since you’ve used extensions, check out the hint for an example extension. You should see an error because TreeNode doesn’t conform to Equatable yet.

2.

Now if your TreeNode was a struct and not a class, this would be all the code you need (check out Apple’s documentation here for more details) but with classes, you need to define your own == method inside the extension.

  • Create the static function == inside the extension, it should have two TreeNode parameters, lhs and rhs and return a Bool. The lhs and rhs relate to the “left-hand side” and “right-hand side” objects of the == sign.
  • Leave the implementation empty for now. You should see an error because the function doesn’t return anything yet.
3.

To meet our defined equality specifications, write a return statement that checks if the data from the lhs node equals the data from the rhs node AND that the children of lhs and rhs are also equal.

You can include the return keyword or not, a single line function will automatically return the result.

4.

Underneath the extension, we’ve added the Edgar Allan Poe Family Tree. Below it, add a print statement checking if both David Poes are the same person (patriarch and child4). Use your newly defined == operator.

5.

There are some flaws in this logic that require customization based on your specific use case of a tree. For example, if both people have the same name and also happen to have no children (leaf nodes), then by our logic they are equal.

  • Print and test the equality of the William Poe’s (child2 and grandchild1).

A possible workaround would be to add another property to TreeNode, such as a birthday, that’s included in the check for equality. For our tree, however, we’ll leave the logic as is.

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?