Helper function add()
template <class T>
void Tree<T>::Iterator::add(Node* root) {
/* first we move to the left child of the root */
Node* node = root->left_;
/* then we traverse all the way to the right, and
adding all the nodes along the way if it is not nullptr*/
while (node != nullptr) {
stk.push(node);
node = node->right_;
}
}
Tree::Iterator constructor
template <class T>
Tree<T>::Iterator::Iterator(Tree::Node *root) : curr_(root) {
// TODO: your code here
/* if root == nullptr, just return it */
if (root == nullptr) {
return;
}
/* add all the nodes from right branch to the stack */
Node* node = root;
while (node != nullptr) {
stk.push(node);
node = node->right_;
}
/* Since the initlization "curr_(root)" is not the place we
want to start, the place we want is at the right most nodes, so we
have to reset curr_ to whatever on the top of the stack (which is
the rightmost node) */
curr_ = stk.top();
stk.pop();
/* check the curr_->data_ != NULL, and during the loop we want
to make sure that stk never goes empty */
while (curr_->data_ == NULL && !stk.empty()) {
curr_ = stk.top(); // replace with top elements
stk.pop(); // remove used nodes
add(curr_); /* add all neighbors from curr_ (or previous top elements)
in the stack */
}
/* if curr_ make to this point, curr_->data != NULL or curr_->data_ is
still NULL, since we do not know nodes in our stack is valid or not,
so we have to do a final check */
if (stk.empty() && curr_->data_ == NULL) {
curr_ = nullptr;
}
/* if code reaches here, curr is not nullptr and curr_->data_ != NULL */
}
Tree::Iterator::operator++
template <class T>
typename Tree<T>::Iterator & Tree<T>::Iterator::operator++() {
// TODO: your code here
/* make sure stack is not empty before traverse */
if (!stk.empty()) {
curr_ = stk.top(); // replace curr_ with top()
stk.pop(); // remove used node from stack
add(curr_); // add curr_'s neighbors
/* same code to check curr_->data_ */
while (curr_->data_ == NULL && !stk.empty()) {
curr_ = stk.top(); // replace with top elements
stk.pop(); // remove used nodes
add(curr_); // add all its neighbors in
}
/* same code to check curr_->data_ */
if (stk.empty() && curr_->data_ == NULL) {
curr_ = nullptr;
}
} else {
curr_ = nullptr; /* set curr_ = nullptr if stack is empty
(which means we are done) */
}
return *this;
}
Tree::Iterator::operator*()
template <class T>
T Tree<T>::Iterator::operator*() const {
// TODO: your code here
/* return default T if curr_ is nullptr (at the end) */
if (curr_ == nullptr) {
return T();
}
/* return the data otherwise */
return curr_->data_;
}