Return to Answer

• Balancing the tree would decrease the worst-case insertion, lookup and deletion costs from \$\mathcal{O}(n)\$ to \$\mathcal{O}(\log n)\$. However, it might increase the average runtime by a constant factor. As always with performance: Measure, measure, measure!
• Trees are notoriously bad regarding cache misses because of all the pointer chasing. Maybe using an arena allocator (aka "object pool" or "region allocator") could help to reduce those.

• Balancing the tree would decrease the worst-case insertion, lookup and deletion costs from \$\mathcal{O}(n)\$ to \$\mathcal{O}(\log n)\$. However, it might increase the average runtime by a constant factor. As always with performance: Measure, measure, measure!
• Trees are notoriously bad regarding cache misses because of all the cache misses due to pointer chasing. Maybe using an arena allocator (aka "object pool" or "region allocator") could help to reduce those cache misses.

• Which traversal order is used by the iterators? The naming doesn't clarify whether it's using in-order, pre-order, post-order, level-order or some different traversal order.
• Rule of 5 violation: copy assignment operator is missing and not declared as deleted.
• Many member function return a bool to indicate whether an operation did some specific work. This usually doesn't matter, as the result would be the same. If it does matter in some case, the relevant information can usually be checked in another way,
• Many member function names deviate from the usual standard library ones. This might lead to confusion, and requires users of the library to add adaptors if they want to use standard library functionality, e.g. algorithms.

• Which traversal order is used by the iterators? The naming doesn't clarify whether it's using in-order, pre-order, post-order, level-order or some different traversal order.
• Rule of 5 violation: copy assignment operator is missing and not declared as deleted.
• Many member function return a bool to indicate whether an operation did some specific work. This usually doesn't matter, as the result would be the same. If it does matter in some case, the relevant information can usually be checked in another way,
• Many member function names deviate from the usual standard library ones. This might lead to confusion, and requires users of the library to add adaptors if they want to use standard library functionality, e.g. algorithms.
• find_node will never return a nullptr, so the implementation could be adjusted to return a node*& (basically, exchange the loop for recursion). This would allow clearer code, as it removes the need for the obscure (*pos)->value syntax (replacement would be pos->value).

#Memory management

• clear might overflow the callstack for large number of nodes if the tree is highly unbalanced.

• Prefer std::unique_ptr over raw owning pointers. binary_search_tree::root, node::left and node::right can easily be replaced with std::unique_ptr<node> without impeding performance. Doing so easily documents the ownership of nodes, thus increasing readability.

• emplace just tramples all over alignment requirements, as alignof(node) (depending on alignof(ValueType)) might be much greater than alignof(char). What prevents a forwarding contructor in node, like this one:

   template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<ValueType, Args...>>>
   node(Args&&... args)
     : value{std::forward<Args>(args)...} {}
  

  Using this constructor would simplify the code in emplace.

• find_replacement accesses start_pos->left after deleting start_pos.

#Correctness

• emplace doesn't check whether ValueType would be constructible from the passed Args.
• try_insert will accept an lvalue reference to a move-only type, or an rvalue reference to a copy-only type.

#Performance

• Balancing the tree would decrease the worst-case insertion, lookup and deletion costs from \$\mathcal{O}(n)\$ to \$\mathcal{O}(\log n)\$. However, it might increase the average runtime by a constant factor. As always with performance: Measure, measure, measure!
• Trees are notoriously bad regarding cache misses because of all the pointer chasing. Maybe using an arena allocator (aka "object pool" or "region allocator") could help to reduce those.

#Interface

• Which traversal order is used by the iterators? The naming doesn't clarify whether it's using in-order, pre-order, post-order, level-order or some different traversal order.
• Rule of 5 violation: copy assignment operator is missing and not declared as deleted.
• Many member function return a bool to indicate whether an operation did some specific work. This usually doesn't matter, as the result would be the same. If it does matter in some case, the relevant information can usually be checked in another way,
• Many member function names deviate from the usual standard library ones. This might lead to confusion, and requires users of the library to add adaptors if they want to use standard library functionality, e.g. algorithms.

#Memory management

• clear and deep_copy might overflow the callstack for large number of nodes if the tree is highly unbalanced.

• Prefer std::unique_ptr over raw owning pointers. binary_search_tree::root, node::left and node::right can easily be replaced with std::unique_ptr<node> without impeding performance. Doing so easily documents the ownership of nodes, thus increasing readability.

• emplace just tramples all over alignment requirements, as alignof(node) (depending on alignof(ValueType)) might be much greater than alignof(char). What prevents a forwarding contructor in node, like this one:

   template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<ValueType, Args...>>>
   node(Args&&... args)
     : value{std::forward<Args>(args)...} {}
  

  Using this constructor would simplify the code in emplace.

• find_replacement accesses start_pos->left after deleting start_pos.

#Correctness

• emplace doesn't check whether ValueType would be constructible from the passed Args.
• try_insert will accept an lvalue reference to a move-only type, or an rvalue reference to a copy-only type.

#Performance

• Balancing the tree would decrease the worst-case insertion, lookup and deletion costs from \$\mathcal{O}(n)\$ to \$\mathcal{O}(\log n)\$. However, it might increase the average runtime by a constant factor. As always with performance: Measure, measure, measure!
• Trees are notoriously bad regarding cache misses because of all the pointer chasing. Maybe using an arena allocator (aka "object pool" or "region allocator") could help to reduce those.

#Interface

• Which traversal order is used by the iterators? The naming doesn't clarify whether it's using in-order, pre-order, post-order, level-order or some different traversal order.
• Rule of 5 violation: copy assignment operator is missing and not declared as deleted.
• Many member function return a bool to indicate whether an operation did some specific work. This usually doesn't matter, as the result would be the same. If it does matter in some case, the relevant information can usually be checked in another way,
• Many member function names deviate from the usual standard library ones. This might lead to confusion, and requires users of the library to add adaptors if they want to use standard library functionality, e.g. algorithms.

#template restrictions

• Prefer error messages with static_assert over SFINAE if a (member) function has no overloads. This helps with debugging and gives better error messages. (SFINAE is still fine if other overloads might be a better fit, as it only removes that candidate from the overload set.)
• Non-templated functions are always a better match than templated function, so the default copy constructor will always be a better match than the templated one. To get a conditional copy constructor, the condition needs to be evaluated at class level (e.g. by inheriting from a dependent base class).