How do I reverse a binary tree?

main.cpp

#include <iostream>
#include <memory>
#include <stack>
#include <utility>

namespace klmr { namespace util { namespace binary_tree {

template <typename T>
using ptr = std::unique_ptr<T>;

template <typename T>
struct node {
    ptr<node<T>> left;
    ptr<node<T>> right;
    T value;

    explicit node(T value) noexcept
        : left{}
        , right{}
        , value{std::move(value)} {}

    node(ptr<node<T>>&& left, ptr<node<T>>&& right, T value) noexcept
        : left{std::move(left)}
        , right{std::move(right)}
        , value{std::move(value)} {}

    node(node const& other)
        : left{other.left ? std::make_unique<node<T>>(*other.left) : nullptr}
        , right{other.right ? std::make_unique<node<T>>(*other.right) : nullptr}
        , value{other.value} {}
};

template <typename T>
struct binary_tree {
    ptr<node<T>> root;

    binary_tree() noexcept : root{} {}

    binary_tree(ptr<node<T>>&& root) noexcept : root{std::move(root)} {}

    binary_tree(binary_tree const& other) :
        root{other.root ? std::make_unique<node<T>>(*other.root) : nullptr} {}
};

template <typename T>
auto make_node(T value) {
    return std::make_unique<node<T>>(value);
}

template <typename T>
auto make_node(ptr<node<T>>&& left, ptr<node<T>>&& right, T value) {
    return std::make_unique<node<T>>(std::move(left), std::move(right), value);
}

template <typename T>
std::ostream& operator <<(std::ostream& out, node<T> const& node) {
    out << '(' << node.value;
    if (node.left) out << ' ' << *node.left;
    if (node.right) out << ' ' << *node.right;
    return out << ')';
}

template <typename T>
std::ostream& operator <<(std::ostream& out, binary_tree<T> const& tree) {
    if (tree.root) out << *tree.root;
    return out;
}

template <typename T>
void reverse_rec(node<T>& node) {
    std::swap(node.left, node.right);
    if (node.left) reverse_rec(*node.left);
    if (node.right) reverse_rec(*node.right);
}

template <typename T>
void reverse_rec(binary_tree<T>& tree) {
    if (tree.root) reverse_rec(*tree.root);
}

template <typename T>
void reverse_iter(binary_tree<T>& tree) {
    std::stack<node<T>*> stack{};
    stack.push(tree.root.get());

    while (not stack.empty()) {
        auto current = stack.top();
        stack.pop();

        if (current == nullptr) continue;

        std::swap(current->left, current->right);
        stack.push(current->left.get());
        stack.push(current->right.get());
    }
}

}}} // klmr::util::binary_tree

using klmr::util::binary_tree::binary_tree;

template <typename T>
void test(binary_tree<T> const& tree) {
    std::cout << "Before: " << tree << '\n';

    binary_tree<T> rev_rec{tree};
    reverse_rec(rev_rec);
    std::cout << "Recursive: " << rev_rec << '\n';

    binary_tree<T> rev_iter{tree};
    reverse_iter(rev_iter);
    std::cout << "Iterative: " << rev_iter << "\n\n";
}

int main() {
    using klmr::util::binary_tree::node;
    using klmr::util::binary_tree::make_node;

    binary_tree<int> a{};
    test(a);

    binary_tree<int> b{make_node(42)};
    test(b);

    binary_tree<int> c{make_node(make_node(2), make_node(3), 1)};
    test(c);

    binary_tree<int> d{
        make_node(
            make_node(2),
            make_node(
                make_node(4),
                make_node(
                    make_node(6),
                    make_node(7),
                    5),
                3),
            1)};
    test(d);
}