C++ Template Binary Search Tree

Question

I've been trying to improve my C++ skills as well as work on some general coding techniques so I've attempted to build my first binary search tree in C++ using templates. I've mostly done Java programming but have worked on some smaller C/C++ projects. There are three things that I'm most concerned with to make sure I'm following proper practices. First is overloading the assignment operator and implementing copy constructors for my Node class, second is making sure I'm following the right practice for a template class, and finally any general feedback about my coding (readability, consistency, clarity, etc.).

I have looked over some of the other questions on here asking for a similar review (and there are a lot) so I've tried to make sure I've followed the advice people provided there. I know one big thing will be the use of raw pointers over shared_ptr or unique_ptr, but I chose to use raw points to force myself to carefully manage memory and I'm in a course that's all in C so the practice can't hurt.

BinarySearchTree.h

#ifndef BinarySearchTree_H
#define BinarySearchTree_H

template<typename T>
class Node{
public:
    Node() : value(), left_child(nullptr), right_child(nullptr) {}
    Node(T value) : value(value), left_child(nullptr), right_child(nullptr) {}
    // Not 100% sure I'm handling these properly
    Node(Node<T> &node) {
        left_child = node.get_left();
        right_child = node.get_right();
        value = node.get_value();
    }
    Node<T>& operator=(Node &node){
        left_child = node.get_left();
        right_child = node.get_right();
        value = node.get_value();
        return this;
    }
    ~Node() {}

    bool operator==(Node<T>* node) {
        return right_child == node->get_right() && left_child == node->get_left() && value == node->get_value();
    }

    void set_left(Node<T> *left) { left_child = left; }
    void set_right(Node<T> *right) { right_child = right; }
    void set_value(T& val) { value = val; }

    Node<T>* get_right() { return right_child; }
    Node<T>* get_left() { return left_child; }

    T get_value() { return value; }

private:
    T value;
    Node *left_child;
    Node *right_child;

};

template<typename T>
class BinarySearchTree {
private:
    Node<T>* root;

    // Recursivle delete all nodes in the tree
    void delete_tree(Node<T>* node){
        if (node) {
            delete_tree(node->get_left());
            delete_tree(node->get_right());
            delete node;
        }
    }

    void insert_subtree(Node<T>* subtree);

public:

    BinarySearchTree<T>() : root(nullptr) {}
    BinarySearchTree<T>(Node<T>* root) : root(root) {}
    ~BinarySearchTree<T>() { delete_tree(root); }   
    // No copy/assignments for this class yet

    void add_node(Node<T>* node);

    bool find_value(T& value);
    bool find_node(Node<T>* node);
    bool update_node(Node<T>* node, T& value);
    bool remove_node(Node<T>* node);
    bool remove_root();

};
#endif

BinarySearchTree.cpp

#include "BinarySeachTree.h"

template<typename T>
void BinarySearchTree<T>::add_node(Node<T>* node) {

    if (!root && !node) {
        return;
    }
    else if (root && !node) {
        return;
    }
    else if (!root && node) {
        root = node;
        return;
    }

    // Walk through the tree until a leaf node is found and add the new node
    Node<T>* walker = root;
    while (walker) {
        if (node->get_value() < walker->get_value()) {
            if (walker->get_left()) {
                walker = walker->get_left();
            }
            else {
                walker->set_left(node);
                return;
            }
        }
        else {
            if (walker->get_right()) {
                walker = walker->get_right();
            }
            else {
                walker->set_right(node);
                return;
            }
        }   
    }
}

template<typename T>
bool BinarySearchTree<T>::remove_root() {
    if (root->get_right()) {
        Node<T>* subtree = root->get_right()->get_left();
        root->get_right()->set_left(root->get_left());
        Node<T>* old_root = root;
        root = root->get_right();
        insert_subtree(subtree);
        delete old_root;
    }
    else {
        if (root->get_left()->get_right()) {
            Node<T>* subtree = root->get_left()->get_right();
            root->get_left()->set_right(root->get_right());
            Node<T>* old_root = root;
            root = root->get_left();
            insert_subtree(subtree);
            delete old_root;
        }
    }
    return true;
}

template<typename T>
bool BinarySearchTree<T>::remove_node(Node<T>* node) {

    // Empty tree, node cannot be removed
    if (!root || !node) {
        return false;
    }

    // If we remove the root we must check to see
    // if there is a subtree to the left, and make it the
    // new root and reinsert the nodes from the new roots
    // old left subtree
    if (node == root) {
        if (root->get_right()) {
            Node<T>* subtree = root->get_right()->get_left();
            root->get_right()->set_left(root->get_left());
            Node<T>* old_root = root;
            root = root->get_right();
            insert_subtree(subtree);
            delete old_root;
        }
        else {
            Node<T>* subtree = root->get_left()->get_right();
            root->get_left()->set_right(root->get_right());
            Node<T>* old_root = root;
            root = root->get_left();
            insert_subtree(subtree);
            delete old_root;
        }
        return true;
    }

    Node<T>* walker = root;
    while (walker) {    
        if (walker->get_value() > node->get_value()) {
            // If the next node to the left is the node we want to remove
            // we check if it has a right element and make that element the new
            // root of the subtree beginning where node was, otherwise move the left
            // subtree up to where node originally was.
            if (walker->get_left() == node) {
                if (walker->get_left()->get_right()) {
                    Node<T>* subtree = walker->get_left()->get_left();
                    walker->set_left(walker->get_left()->get_right());
                    walker->get_left()->set_left(subtree);
                    delete node;
                    return true;
                }
                else {
                    Node<T>* subtree = walker->get_left()->get_left();
                    walker->set_left(subtree);
                    delete node;
                    return true;
                }
            }
            else {
                walker = walker->get_left();
            }
        }
        else {
            // Same idea as above working down the right subtree
            if (walker->get_right() == node) {
                if (walker->get_right()->get_left()) {
                    Node<T>* subtree = walker->get_right()->get_right();
                    walker->set_right(walker->get_right()->get_left());
                    walker->get_right()->set_right(subtree);
                    delete node;
                    return true;
                }
                else {
                    Node<T>* subtree = walker->get_right()->get_right();
                    walker->set_right(subtree);
                    delete node;
                    return true;
                }
            }
            else {
                walker = walker->get_right();
            }
        }       
    }
    // Could not find the node to remove
    return false;
}

// Recursively adds all nodes in the subtree to the tree again
template<typename T>
void BinarySearchTree<T>::insert_subtree(Node<T>* subtree) {

    if (subtree) {
        add_node(subtree->get_left());
        add_node(subtree->get_right());
        add_node(subtree);
    }

}

// Determines if a node exists in the tree with the given value
template<typename T>
bool BinarySearchTree<T>::find_value(T& value) {

    if (!root) {
        return false;
    }

    Node<T>* walker = root;
    while (walker) {
        if (value > walker->get_value()) {
            walker = walker->get_right();
        }
        else if (value < walker->get_value()) {
            walker = walker->get_left();
        }
        else {
            return true;
        }
    }

    return false;
}

// Determines if the given node exists in the tree
template<typename T>
bool BinarySearchTree<T>::find_node(Node<T>* node) {

    if (!root || !node) {
        return false;
    }

    Node<T>* walker = root;
    while (walker) {
        if (node->get_value() > walker->get_value()) {
            walker = walker->get_right();
        }
        else if (node->get_value() < walker->get_value()) {
            walker = walker->get_left();
        }
        else {
            return true;
        }
    }

    return false;
}

// Search the tree until the find the given node, create and insert a node
// with the given value and remove the old node.
template<typename T>
bool BinarySearchTree<T>::update_node(Node<T>* node, T& value) {

    if (!node) {
        return false;
    }

    Node<T>* walker = root;
    while (walker) {
        if (node->get_value() > walker->get_value()) {
            walker = walker->get_right();
        }
        else if (node->get_value() < walker->get_value()) {
            walker = walker->get_left();
        }
        else {
            if (node == walker) {
                // Create a new node with the given value, remove the old
                // node and add the new one.
                Node<T>* new_node = new Node<T>(value);
                remove_node(node);
                add_node(new_node);
                return true;
            }
            else {
                // Right value but wrong node (duplicate)
                walker = walker->get_right();
            }
        }
    }

    return false;
}

Answer 1

I see a few main issues with your code:

1) the viewability of your Node<T>s to outside code as well as your implementation of the copy constructor and assignment operator 2) the API of the BST/Node<T>s. 3) recursive algorithms (which are not optimal for large trees).

Refactor Nodes

If I decide to use your BST, I have to know that I need to create Node<T>. This is not good OO design as the Nodes are an implementation detail that need to be hidden from the user unless there is a good reason to expose the user to them. The solution here would be to encapsulate the Nodes within your BST class and make the BST handle all the finer details of managing the Nodes. Also, your Node class is unncessarily complex and verbose. For example, you could have a single constructor for Node that default assigns the left and right sub-child pointers to nullptr if no value is provided to it. I would also remove the encapsulation in the class and just make its members public. This isn't a violation of good OO design since the parent class (BST) will be managing all of the Nodes and the user won't have direct access to any of the nodes (ever).

template <class T>
class BST {
    struct Node {
        Node(const T& value, Node *left = nullptr, Node *right = nullptr)
            : data(value), left(left), right(right) {}
        ~Node() {}
        Node(const Node<T> &other); // see below
        Node& operator=(Node<T> other); // see below
        void swap(Node<T> &other); // see below
        T data;
        Node *left, *right;
    };
public:
    // BST public methods here
};

Node copy constructor / assignment operator

The versions that you implemented are essentially the compiler-provided default implementations. Remember that when dynamic memory and pointers are involved, copy constructors and assignment operators usually need to make a deep copy of the data they are pointing to. Use the copy-and-swap idiom for this:

// here we use the constructor that I provided above
Node(const Node<T> &other)
{
    data = other.data;
    left = new Node(other.left->data, other.left->left, other.left->right);
    right = new Node(other.right->data, other.right->left, other.right->right);
}

// implement a swap function for the Nodes (need to include <algorithm>)
void Node<T>::swap(Node<T> &other)
{
    std::swap(data, other.data);
    std::swap(left, other.left);
    std::swap(right, other.right);
}

// notice the copy in the parameter.
Node<T>& operator=(Node<T> other)
{
    swap(other);
    return *this;
}

BST API

Again, your BST's API exposes the implementation details unnecessarily by letting the user be responsible for passing in a Node to add. The BST should be responsible for adding/removing/managing any and all nodes. It would be much more efficient if the user could just pass in a value that they would like to add. Moreover, the user should not be provided with an option to remove the root of the tree or any other element of the tree. The API should just have a remove() function that takes care of any details of removing an element from the tree (whether or not that element was the root of the tree or not). Also, the BST is organized based on an ordering criterion so allowing the user to update the value of a node already in a tree is not a good idea as that can break the order that the tree is built on. For simplicity's sake, the API should really be:

template <class T>
class BST {
    // all the struct stuff from above
    Node<T> *root;
public:
    BST() : root(nullptr) {}
    ~BST() { /* implement */ }
    bool insert(const T& value);
    bool remove(const T& value);
    bool find(const T &value);
};

All the user has to do is just provide a value to add/remove/find from the tree. Then BST then takes care of all the details and the user doesn't need to worry about anything.

Recursion

Although recursion is a simple way to implement trees, it becomes a big hit to performance once you construct a moderately large tree (which can be often). I would look into making iterative versions of your recursive functions (particularly the insert and destroy tree functions).