Binary tree traversal - C++ 17 implementation.

binary-tree-traversal.cpp

#include <map>
#include <array>
#include <string>
#include <vector>
#include <memory>
#include <sstream>
#include <cassert>
#include <iostream>
#include <exception>

namespace {

template <typename T, typename V>
struct Node {
    T key_;
    V value_;
    std::unique_ptr<Node<T, V>> left_;
    std::unique_ptr<Node<T, V>> right_;

    explicit Node(const T& key, const V& value)
        : key_{ key }, value_{ value } {}
};

} // namespace

template <typename T, typename V>
class BinaryTree {
    using node_t = Node<T, V>;
    using leaf_t = std::unique_ptr<node_t>;

    leaf_t root_;

    void insert(const T& key, const V& value, leaf_t& leaf) {
        if (!leaf)
            leaf = std::make_unique<node_t>(key, value);
        else if (key == leaf->key_)
            leaf->value_ = value;
        else if (key < leaf->key_)
            insert(key, value, leaf->left_);
        else if (key > leaf->key_)
            insert(key, value, leaf->right_);
    }

    V& find(const T& key, const leaf_t& leaf) const {
        if (!leaf) throw std::exception("not found");

        if (key == leaf->key_)
            return leaf->value_;
        else if (key < leaf->key_)
            return find(key, leaf->left_);
        else
            return find(key, leaf->right_);
    }

    std::string toString(const leaf_t& leaf) {
        if (!leaf) return "";
        std::stringstream ss;
        if (leaf->left_) ss << toString(leaf->left_);
        ss << leaf->key_ << ':' << leaf->value_ << '\n';
        if (leaf->right_) ss << toString(leaf->right_);
        return ss.str();
    }

public:
    void insert(const T& key, const V& value) {
        insert(key, value, root_);
    }

    V& find(T key) const {
        return find(key, root_);
    }

    std::string toString() {
        return toString(root_);
    }
};

int main() {
    BinaryTree<int, int> map;
    map.insert(10, 20);
    map.insert(10, 20);
    map.insert(11, 21);
    map.insert(9, 19);
    map.insert(12, 22);
    map.insert(13, 23);
    map.insert(8, 18);
    map.insert(5, 15);

    try {
        auto res = map.find(10);
        assert(res == 20);
    } catch (std::exception e) {
        std::cout << e.what() << '\n';
    }
    std::cout << map.toString();
}