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)