Skip to main content
Code Review

Return to Question

edited tags
Link
200_success
200_success
  • 144.2k
  • 22
  • 188
  • 473
added 22 characters in body
Source Link
between_lines
between_lines
  • 33
  • 1
  • 5
#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;
}

#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;
        }
    }
}

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;
}

#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;
}
Source Link
between_lines
between_lines
  • 33
  • 1
  • 5

C++ Template Binary Search Tree

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;
        }
    }
}

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;
}