Binary search tree in C++ 17 using iterator pattern
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)