template <typename T>
TreeSet<T>::const_iterator TreeSet<T>::lower_bound(
    const T& key) const {
    // We use end() to make an iterator with an empty stack, and then
    // the helper function builds the iterator's final value by pushing
    // nodes onto the stack as it searches for the lower bound.
    const_iterator iter = end();
    return nodeLowerBound(root_, key, iter);
}

template <typename T>
TreeSet<T>::const_iterator TreeSet<T>::nodeLowerBound(
    Node* currentNode, const T& key, const_iterator& iter) {
    // The goal:
    // - Find the first node in the tree whose value is >= key and return
    //   an iterator pointing to it.
    // How it works:
    // - Recall that an iterator is represented by a stack consisting of all
    //   the parent nodes that are greater than (or equal to for the top of the
    //   stack) the node where the iterator currently is.
    // - Imagine our tree holds ints, we're looking for lower_bound(7), and
    //   suppose the current node is
    //     - 5: since 5 < 7, we know that all nodes in the left subtree
    //          are also < 7, so we can skip them and go right.
    //     - 10: since 10 >= 7, we know that 10 is a potential lower bound,
    //          so we push it onto the stack and go left to see if there's
    //          a smaller candidate.
    //     - 7: we could have an explicit check for equality, push 7, and
    //          terminate the search early, but it's not necessary; we can just
    //          treat it like the 10 case above, pushing and going left. All
    //          nodes in the left subtree will be < 7, so we'll eventually
    //          exhaust that subtree and return the iterator with 7 on top
    //          of the stack.
    //     - nullptr: we've reached the end of a subtree; we return the
    //          iterator we've built so far.

    if (currentNode == nullptr) {
        // Return whatever iterator value we've built so far.
        return iter;
    }

    if (currentNode->value_ < key) {
        // Current node is less than key, but we need a value >= key.
        // Go right to find a larger candidate.
        return nodeLowerBound(currentNode->right_, key, iter);
    } else {
        // Current node is >= key, so it's a potential lower bound.
        // Push it onto the stack and go left to see if there's a smaller
        // candidate, since we want the least such node.
        iter.stack_.push(currentNode);
        return nodeLowerBound(currentNode->left_, key, iter);
    }
}