# Binary search tree in C++ 17 using iterator pattern

I am new to C++ and am attempting to write the following binary search tree using the iterator pattern (and std::optional in C++17):

#include <memory>
#include <optional>
#include <stack>

template <typename T>
class BinarySearchTree {
public:
BinarySearchTree(T key)
: key_(key),
left_(nullptr),
right_(nullptr) {}

BinarySearchTree(const BinarySearchTree& bst) {
key_ = bst.key_;
left_ = std::make_unique<BinarySearchTree>(*bst.left_);
right_ = std::make_unique<BinarySearchTree>(*bst.right_);
}

void insert(T key);

T key() { return key_; }
std::unique_ptr<BinarySearchTree> left() { return std::make_unique<BinarySearchTree>(*left_); }
std::unique_ptr<BinarySearchTree> right() { return std::make_unique<BinarySearchTree>(*right_); }

private:
T key_;
std::unique_ptr<BinarySearchTree> left_;
std::unique_ptr<BinarySearchTree> right_;
};

template <typename T>
void BinarySearchTree<T>::insert(T key) {
auto insert = [key](auto& node) {
if (node) {
node->insert(key);
} else {
node = std::make_unique<BinarySearchTree>(key);
}
};

if (key <= key_) {
insert(left_);
} else {
insert(right_);
}
}

template <typename T>
class BinarySearchTreeIterator {
public:
BinarySearchTreeIterator(BinarySearchTree<T>& bst, bool forward)
: bst_(std::make_unique<BinarySearchTree<T>>(bst)),
forward_(forward) {}

std::optional<T> operator*() { return current_; }

void operator++() {
while (bst_ || !stack_.empty()) {
if (bst_) {
stack_.emplace(std::make_unique<BinarySearchTree<T>>(*bst_));
bst_ = std::make_unique<BinarySearchTree<T>>(*(forward_ ? bst_->left() : bst_->right()));
} else {
bst_ = std::make_unique<BinarySearchTree<T>>(*(stack_.top()));
stack_.pop();
current_ = bst_->key();
bst_ = std::make_unique<BinarySearchTree<T>>(*(forward_ ? bst_->right() : bst_->left()));
break;
}
}
}

private:
std::unique_ptr<BinarySearchTree<T>> bst_;
bool forward_;
std::stack<std::unique_ptr<BinarySearchTree<T>>> stack_;
std::optional<T> current_;
};


I am not sure if my usage of std::unique_ptr is correct or idiomatic.

# BinarySearchTree

• Since the tree isn't balanced, worst case insertion complexity is $\mathcal{O}(n)$ (and not $\mathcal{O}(\log n)$ as likely intended). (Same for lookup, if such a method were to be added).
• Calling left() or right() will create a copy of the whole left/right subtree. This is very likely not intended.
• This class could profit a lot from a move constructor and a move assignment operator overload. (And while we're at it, add a copy assignment operator overload and a destructor to complete the rule of five.)
• Is it really necessary to name the lambda the same as the enclosing function in BinarySearchTree::insert(T key)?
• Also of note, only types that can be copied can be inserted into the BinarySearchTree. This means it is currently not possibly to store a move-only type (like std::unique_ptr) in the tree. (This capacity could be added with an overload accepting a T&&.
• BinarySearchTree::insert(T key) creates unnecessary copies of key for each recursive call. Consider taking a const T& instead.
• left_ and right_ are often dereferenced without checking them for nullptr beforehand! This results in undefined behavior if they are nullptr!

# BinarySearchTreeIterator

• This iterator doesn't provide any iterator_traits or an end iterator. This means using it with standard library algorithms (or even a range based for loop) is not possible. More info on iterators and iterator_traits.
• There are lots and lots of unnecessary copies (basically every time std::make_unique or bst_->left() or bst_->right() are called).
• current_ will always have a value with this implementation, so making it std::optional<T> is misleading. Also, any modifications done to the value returned by operator*() won't be propagated to the original BinarySearchTree entry (as it returns an independent copy and not a reference).
• This iterator traverses the tree in-order. Since there are also other traversal methods, like pre-order, post-order or level-order, it would be nice to indicate that in the name.

# std::unique_ptr usage

Normally, a std::unique_ptr is used to express "I own this". So a signature like std::unique_ptr<BinarySearchTree<T>> BinarySearchTree::left() says "Call me, and you become the new owner of whatever I return".

Is this necessary in this case? No! After all, the caller just wants to access the existing object, and not acquire a new one.

So, how can this be expressed?

There are two variants:

1. Return a non-owning BinarySearchTree<T>*.

Pros:

• Very lightweight.
• Very simple (can still use std::unique_ptr for internal storage, so resources get cleaned up properly).

Cons:

• If the BinarySearchTree<T> gets destroyed, but someone still has the pointer stored, the pointer is dangling.
• Someone could prematurely call delete on the pointer (so the internal std::unique_ptr would be dangling).
2. Return a std::shared_ptr<BinarySearchTree<T>>.

Pros:

• As long as the std::shared_ptr exists, the object will be valid.

Cons:

• Might keep the tree (or subtrees) alive for far longer than intended.
• Requires using std::shared_ptr for internal storage.
Of course, some of those problems can be avoided by appropriate use of std::weak_ptr.
• @EmilyL.: The node might be nullptr, though, so you'd return a dangling reference in those cases. Sadly, there are no std::optional<T&> :/ – hoffmale Nov 19 '17 at 11:09
• @EmilyL.: Oh, yeah. I was so taken in with all the extra copies that I completely overlooked the nullptr` dereferences. – hoffmale Nov 20 '17 at 7:30