Tree (In)Equality
In this phase, you'll be able to compare two TreeStringSet objects to see if they're equal. Trees are equal if they contain the same items, regardless of their shape.
This part will be a good chance to put your new iterator to use.
Your Task…
Following the four steps of our development process (Plan, Write Tests, Implement, Test & Fix), implement the following member functions from the TreeStringSet class:
operator==operator!=
These functions are described in the TreeStringSet Specification.
No Planning Image Required
You don't need to do a planning image for this phase. (See the hints below for why!)
Equality the Easy Way!
There is a really straightforward way to implement equality.
Because we have an iterator that goes though the items in the tree in sorted order, we can just use that iterator with the standard-library algorithm std::equal. It takes four arguments: a start/past-end pair for the first iterator, and a second start/end pair for the second iterator. std::equal returns true if both iterators have the same number of elements and all of those elements are equal.
(You can instead iterate through both trees manually if you prefer.)
This function is required to take \( \mathrm{O}(n) \) time, where \( n \) is the size of the smallest tree. A straightforward implementation using your iterator will meet this bound.
To use
std::equal, you need#include <algorithm>
Planning-Process Reminders
See Phase 1 for a reminder of the four steps (planning, writing tests, implementing, verifying) that you should go through, and of what we’re looking for in each.
(When logged in, completion status appears here.)