Invert binary tree

btree.cpp

#include "btree.h"


template <typename T>
void Btree<T>::insert(const T &x) {
    if (root == nullptr) {
        node_ptr node = std::make_unique<Node>(x);
        root = std::move(node);
        return;
    }

    insert_node(x, root);
}

template <typename T>
void Btree<T>::insert_node(const T &x, node_ptr &p) {
    if (p == nullptr) {
        node_ptr node = std::make_unique<Node>(x);
        p = std::move(node);
        return;
    }

    // No duplicate entries
    if (x < p->value) {
        insert_node(x, p->left);
    } else if (x > p->value ) {
        insert_node(x, p->right);
    }
}

template <typename T>
void Btree<T>::invert() {
    if (root == nullptr) {
        return;
    }

    invert_node(root);
}

template <typename T>
void Btree<T>::invert_node(node_ptr &p) {
    if (p == nullptr) {
        return;
    }


    node_ptr holding = std::move(p->left);
    p->left = std::move(p->right);
    p->right = std::move(holding);

    invert_node(p->left);
    invert_node(p->right);
}

template <typename T>
std::vector<T> Btree<T>::traverse(bool inorder) const {
    typename std::vector<T> xs;

    if (root == nullptr) {
        return xs;
    }

    inorder ? traverse_inorder(root, xs) : traverse_preorder(root, xs);
    return xs;
}

template <typename T>
void Btree<T>::traverse_inorder(const node_ptr &p, std::vector<T> &x) const {
    if (p == nullptr) {
        return;
    }

    traverse_inorder(p->left, x);
    x.push_back(p->value);
    traverse_inorder(p->right, x);
}

template <typename T>
void Btree<T>::traverse_preorder(const node_ptr &p, std::vector<T> &x) const {
    if (p == nullptr) {
        return;
    }

    x.push_back(p->value);
    traverse_preorder(p->left, x);
    traverse_preorder(p->right, x);
}

// Compile a couple data types
template class Btree<int>;
template class Btree<float>;

btree.h

#ifndef __B_TREE_H
#define __B_TREE_H

#include <memory>
#include <vector>


template <typename T>
class Btree {
public:
    Btree() {};

    void insert(const T &x);
    void invert();
    std::vector<T> traverse(bool inorder) const;

private:
    struct Node {
        std::unique_ptr<Node> left, right;
        T value;

        Node(const T &x) : value(x) {}
    };

    typedef std::unique_ptr<Node> node_ptr;

    node_ptr root;

    void insert_node(const T &x, node_ptr &p);
    void invert_node(node_ptr &p);
    void traverse_inorder(const node_ptr &p, std::vector<T> &x) const;
    void traverse_preorder(const node_ptr &p, std::vector<T> &x) const;
};


#endif

main.cpp

#include "btree.h"

#include <iostream>
#include <vector>

int main () {

    std::vector<int> xs = {10, 2, 15, 1, 5, 11, 20};

    Btree<int> tree;

    for (auto &x: xs) {
        tree.insert(x);
    }

    tree.invert();

    // Inorder traversal
    auto v = tree.traverse(true);

    for (auto &x: v) {
        std::cout << x << std::endl;
    }

}