Binary search tree in C++ 17 using iterator pattern

Question

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.

Answer 1

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.
   • Has a slight overhead.
   • Requires using std::shared_ptr for internal storage.
   • Might leak in case of cycles (not a problem here, just for the general case).

   Of course, some of those problems can be avoided by appropriate use of std::weak_ptr.

Some more resources:

• CppCon 2014 talk about smart pointers
• CppCon 2016 talk about memory management (even talks specifically about trees and graphs)

• Emily L.: I would prefer turning a reference from left/right as it makes it clear that it is not a pointer that you should store because it can be destroyed at any point
• hoffmale: @EmilyL.: The node might be nullptr, though, so you'd return a dangling reference in those cases. Sadly, there are no std::optional<T&> :/
• Emily L.: Now that you mention it yes. But that's also a problem with ops current code that directly dereferences and copy constructs from a possibly null-ptr.
• hoffmale: @EmilyL.: Oh, yeah. I was so taken in with all the extra copies that I completely overlooked the nullptr dereferences.