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 &lt;memory&gt;
#include &lt;optional&gt;
#include &lt;stack&gt;

template &lt;typename T&gt;
class BinarySearchTree {
public:
  BinarySearchTree(T key)
  : key_(key),
    left_(nullptr),
    right_(nullptr) {}

  BinarySearchTree(const BinarySearchTree&amp; bst) {
    key_ = bst.key_;
    left_ = std::make_unique&lt;BinarySearchTree&gt;(*bst.left_);
    right_ = std::make_unique&lt;BinarySearchTree&gt;(*bst.right_);
  }

  void insert(T key);

  T key() { return key_; }
  std::unique_ptr&lt;BinarySearchTree&gt; left() { return std::make_unique&lt;BinarySearchTree&gt;(*left_); }
  std::unique_ptr&lt;BinarySearchTree&gt; right() { return std::make_unique&lt;BinarySearchTree&gt;(*right_); }

private:
  T key_;
  std::unique_ptr&lt;BinarySearchTree&gt; left_;
  std::unique_ptr&lt;BinarySearchTree&gt; right_;
};

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

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

template &lt;typename T&gt;
class BinarySearchTreeIterator {
public:
  BinarySearchTreeIterator(BinarySearchTree&lt;T&gt;&amp; bst, bool forward)
  : bst_(std::make_unique&lt;BinarySearchTree&lt;T&gt;&gt;(bst)),
    forward_(forward) {}

  std::optional&lt;T&gt; operator*() { return current_; }

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

private:
  std::unique_ptr&lt;BinarySearchTree&lt;T&gt;&gt; bst_;
  bool forward_;
  std::stack&lt;std::unique_ptr&lt;BinarySearchTree&lt;T&gt;&gt;&gt; stack_;
  std::optional&lt;T&gt; 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&amp;&amp;.
BinarySearchTree::insert(T key) creates unnecessary copies of key for each recursive call. Consider taking a const T&amp; 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_-&gt;left() or bst_-&gt;right() are called).
current_ will always have a value with this implementation, so making it std::optional&lt;T&gt; 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&lt;BinarySearchTree&lt;T&gt;&gt; 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:


Return a non-owning BinarySearchTree&lt;T&gt;*.

Pros:


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


Cons:


If the BinarySearchTree&lt;T&gt; 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).

Return a std::shared_ptr&lt;BinarySearchTree&lt;T&gt;&gt;.

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)