3
\$\begingroup\$

This BST implementation seems to work, I would appreciate an advice on how to improve the code. I am also interested in the following:

  • rule-of-5 methods, are all of them necessary (e.g. is destructor necessary when using smart pointers)? Are they implemented correctly?
  • Does Node class need rule-of-5 methods?
  • is clear() method implemented correctly? I think that if I set the root to nullptr, the rest of the Nodes will be deleted by the smart pointer's destructor when the BinarySearchTree and therefore the Node go out of scope, is it correct?
  • Is the use of smart/raw pointers correct? I want to use raw pointers everywhere, where they don't need to own the object, right?
  • const correctness

Any other advice will be appreciated too.

BinarySearchTree.hpp

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <iostream>
#include <vector>
#include <queue>

class BinarySearchTree {

public:
    BinarySearchTree();
    BinarySearchTree(const int& value);
    BinarySearchTree(const BinarySearchTree& other_tree);
    BinarySearchTree(BinarySearchTree&& other_tree);
    BinarySearchTree& operator=(const BinarySearchTree& other_tree);
    BinarySearchTree& operator=(BinarySearchTree&& other_tree);
    ~BinarySearchTree();

    void build_from_vector(std::vector<int>& values);
    void build_from_vector_balanced(std::vector<int>& values);
    void insert_node(const int& value);
    void remove_node(const int& value);
    void clear();

    int min_val() const;
    int max_val() const;
    bool contains(const int& val) const;

    int max_depth() const;
    bool balanced() const;

    std::vector<int> get_inorder_vals() const;
    std::vector<int> get_preorder_vals() const;
    std::vector<int> get_postorder_vals() const;
    std::vector<int> get_level_order_vals() const;

    inline int size() const {
        return tree_size;
    }
    inline bool empty() const {
        return tree_size == 0;
    }

private:
    struct Node {
        int val;
        std::unique_ptr<Node> left = nullptr;
        std::unique_ptr<Node> right = nullptr;

        Node(const int value) :
        val{value},
        left{nullptr},
        right{nullptr}
        {}
    };

    std::unique_ptr<Node> root;
    int tree_size;

    void deep_copy_tree(std::unique_ptr<Node>& dest_node, const std::unique_ptr<Node>& source_node);

    void build_from_vector_balanced(std::vector<int>::iterator it_b, std::vector<int>::iterator it_e);
    void insert_node(const int& value, std::unique_ptr<Node>& curr_node);
    void remove_node(const int value, std::unique_ptr<Node>& curr_node);

    Node* find_min_node(const std::unique_ptr<Node>& curr_node) const;
    Node* find_max_node(const std::unique_ptr<Node>& curr_node) const;
    bool contains(const int& value, const std::unique_ptr<Node>& curr_node) const;

    bool balanced(const std::unique_ptr<Node>& curr_node, int& height) const;
    int max_depth(const std::unique_ptr<Node>& curr_node) const;

    void get_inorder_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;
    void get_preorder_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;
    void get_postorder_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;
    void get_level_order_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;

};

#endif /* BINARYSEARCHTREE_H */

BinarySearchTree.cpp

#include "BinarySearchTree.hpp"

BinarySearchTree::BinarySearchTree() : root{nullptr}, tree_size{0}
{}

BinarySearchTree::BinarySearchTree(const int& value) : root{std::make_unique<Node>(value)}, tree_size{1}
{}

BinarySearchTree::BinarySearchTree(const BinarySearchTree& other_tree) {
    if (other_tree.tree_size == 0) return;
    tree_size = other_tree.tree_size;
    deep_copy_tree(root, other_tree.root);
}

BinarySearchTree::BinarySearchTree(BinarySearchTree&& other_tree) :
root(std::exchange(other_tree.root, nullptr)), tree_size(std::exchange(other_tree.tree_size, 0))
{
}

BinarySearchTree& BinarySearchTree::operator=(const BinarySearchTree& other_tree) {
    clear();
    tree_size = other_tree.tree_size;
    deep_copy_tree(root, other_tree.root);
    return *this;
}

BinarySearchTree& BinarySearchTree::operator=(BinarySearchTree&& other_tree) {
    clear();
    tree_size = other_tree.tree_size;
    deep_copy_tree(root, other_tree.root);

    other_tree.tree_size = 0;
    other_tree.root = nullptr;

    return *this;
}

BinarySearchTree::~BinarySearchTree() {
    clear();
}

void BinarySearchTree::build_from_vector(std::vector<int>& values) {
    for (const int& value : values) {
        insert_node(value);
    }
}

void BinarySearchTree::build_from_vector_balanced(std::vector<int>& values) {
    std::sort(values.begin(), values.end());
    std::vector<int>::iterator it_b = values.begin();
    std::vector<int>::iterator it_e = values.end() - 1;
    build_from_vector_balanced(it_b, it_e);
}

void BinarySearchTree::insert_node(const int& value) {
    insert_node(value, root);
}

void BinarySearchTree::remove_node(const int& value) {
    remove_node(value, root);
}

void BinarySearchTree::clear() {
    root = nullptr;
    tree_size = 0;
}

int BinarySearchTree::min_val() const {
    return find_min_node(root)->val;
}

int BinarySearchTree::max_val() const {
    return find_max_node(root)->val;
}

bool BinarySearchTree::contains(const int& val) const {
    return contains(val, root);
}

int BinarySearchTree::max_depth() const {
    return max_depth(root);
}

bool BinarySearchTree::balanced() const {
    int height = 0;
    return balanced(root, height);
}

std::vector<int> BinarySearchTree::get_inorder_vals() const {
    std::vector<int> vals;
    get_inorder_vals(vals, root);
    return vals;
}

std::vector<int> BinarySearchTree::get_preorder_vals() const {
    std::vector<int> vals;
    get_preorder_vals(vals, root);
    return vals;
}

std::vector<int> BinarySearchTree::get_postorder_vals() const {
    std::vector<int> vals;
    get_postorder_vals(vals, root);
    return vals;
}

std::vector<int> BinarySearchTree::get_level_order_vals() const {
    std::vector<int> vals;
    get_level_order_vals(vals, root);
    return vals;
}

void BinarySearchTree::deep_copy_tree(std::unique_ptr<Node>& dest_node, const std::unique_ptr<Node>& source_node) {
    if (!source_node) return;
    dest_node = std::make_unique<Node>(source_node->val);
    deep_copy_tree(dest_node->left, source_node->left);
    deep_copy_tree(dest_node->right, source_node->right);
}

void BinarySearchTree::build_from_vector_balanced(std::vector<int>::iterator it_b, std::vector<int>::iterator it_e) {
    if (it_b > it_e) return;

    int range = std::distance(it_b, it_e);
    std::vector<int>::iterator it_m = it_b + range / 2;

    insert_node(*it_m);

    build_from_vector_balanced(it_b, it_m - 1);
    build_from_vector_balanced(it_m + 1, it_e);
}

void BinarySearchTree::insert_node(const int& value, std::unique_ptr<Node>& curr_node) {        
    if (!curr_node) {
        curr_node = std::make_unique<Node>(value);
        tree_size++;
        return;
    }

    if (value == curr_node->val) 
        return;

    if (value < curr_node->val)
        insert_node(value, curr_node->left);
    else // (value > curr_node->val)
        insert_node(value, curr_node->right);
}

void BinarySearchTree::remove_node(const int value, std::unique_ptr<Node>& curr_node) {
    if (!curr_node) return;

    if (value < curr_node->val) {
        remove_node(value, curr_node->left);
    } else if (value > curr_node->val) {
        remove_node(value, curr_node->right);
    } else { // (value == curr_node->val)
        // remove it
        if (!curr_node->left && !curr_node->right) { // leaf
            tree_size--;
            curr_node = nullptr;
        } else if (curr_node->left && !curr_node->right) { // only left child
            tree_size--;
            curr_node = std::move(curr_node->left);
        } else if (!curr_node->left && curr_node->right) { // only right child
            tree_size--;
            curr_node = std::move(curr_node->right);
        } else {
            // both right and left children: replace val by left subtree's max value
            Node* temp = find_max_node(curr_node->left); // ok to have raw pointer here?
            curr_node->val = temp->val;
            // then remove left subtree's max node
            remove_node(temp->val, curr_node->left);
        }
    }
}

BinarySearchTree::Node* BinarySearchTree::find_min_node(const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return nullptr;
    if (!curr_node->left) return curr_node.get();
    return find_min_node(curr_node->left);
}

BinarySearchTree::Node* BinarySearchTree::find_max_node(const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return nullptr;
    if (!curr_node->right) return curr_node.get();
    return find_max_node(curr_node->right);
}

bool BinarySearchTree::contains(const int& value, const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return false;
    if (value == curr_node->val) return true;
    if (value < curr_node->val) return contains(value, curr_node->left);
    return contains(value, curr_node->right);
}

bool BinarySearchTree::balanced(const std::unique_ptr<Node>& curr_node, int& height) const {
    if (!curr_node) {
        height = -1;
        return true;
    }
    int left = 0;
    int right = 0;
    if (balanced(curr_node->left, left)
        && balanced(curr_node->right, right)
        && std::abs(left - right) < 2) {
        height = std::max(left, right) + 1;
        return true;
    }
    return false;
}

int BinarySearchTree::max_depth(const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return -1;
    return std::max(max_depth(curr_node->left), max_depth(curr_node->right)) + 1;
}

void BinarySearchTree::get_inorder_vals(std::vector<int>& vals,
                                        const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;
    get_inorder_vals(vals, curr_node->left);
    vals.push_back(curr_node->val);
    get_inorder_vals(vals, curr_node->right);
}

void BinarySearchTree::get_preorder_vals(std::vector<int>& vals,
                                         const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;
    vals.push_back(curr_node->val);
    get_preorder_vals(vals, curr_node->left);
    get_preorder_vals(vals, curr_node->right);
}

void BinarySearchTree::get_postorder_vals(std::vector<int>& vals,
                                          const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;
    get_postorder_vals(vals, curr_node->left);
    get_postorder_vals(vals, curr_node->right);
    vals.push_back(curr_node->val);
}

void BinarySearchTree::get_level_order_vals(std::vector<int>& vals,
                                            const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;

    std::queue<Node*> nodes_by_level;
    nodes_by_level.push(curr_node.get());
    while (!nodes_by_level.empty()) {
        Node* temp_node = nodes_by_level.front();
        nodes_by_level.pop();

        if (temp_node->left) nodes_by_level.push(temp_node->left.get());
        if (temp_node->right) nodes_by_level.push(temp_node->right.get());

        vals.push_back(temp_node->val);
    }
}

main.cpp

int main() {
    std::cout << "=== BINARY SEARCH TREE ===\n";

    std::cout << "--------------------------\n";
    std::cout << "Build unbalanced vs balanced" << std::endl;
    BinarySearchTree myBST_unb;
    BinarySearchTree myBST_b;
    std::vector<int> values_sorted_back {9, 8, 7, 6, 5, 4, 3, 2, 1};
    myBST_unb.build_from_vector(values_sorted_back);
    myBST_b.build_from_vector_balanced(values_sorted_back);

    std::cout << "Is balanced myBST_unb: " << myBST_unb.balanced() << std::endl;
    std::cout << "Is balanced myBST_b: " << myBST_b.balanced() << std::endl;
    std::cout << "Max depth myBST_unb: " << myBST_unb.max_depth() << std::endl;
    std::cout << "Max depth myBST_b: " << myBST_b.max_depth() << std::endl;

    std::cout << "myBST_unb size: " << myBST_unb.size() << std::endl;
    std::cout << "myBST_unb empty? " << myBST_unb.empty() << std::endl;
    std::cout << "myBST_b size: " << myBST_b.size() << std::endl;
    std::cout << "myBST_b empty? " << myBST_b.empty() << std::endl;

    // Traversals:
    std::vector<int> vals_inorder_unb = myBST_unb.get_inorder_vals();
    std::vector<int> vals_preorder_unb = myBST_unb.get_preorder_vals();
    std::vector<int> vals_postorder_unb = myBST_unb.get_postorder_vals();
    std::vector<int> vals_level_order_unb = myBST_unb.get_level_order_vals();

    std::vector<int> vals_inorder_b = myBST_b.get_inorder_vals();
    std::vector<int> vals_preorder_b = myBST_b.get_preorder_vals();
    std::vector<int> vals_postorder_b = myBST_b.get_postorder_vals();
    std::vector<int> vals_level_order_b = myBST_b.get_level_order_vals();

    std::cout << "Inorder values myBST_unb: " << std::endl;
    for (auto& val : vals_inorder_unb)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Preorder values myBST_unb: " << std::endl;
    for (auto& val : vals_preorder_unb)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Postorder values myBST_unb: " << std::endl;
    for (auto& val : vals_postorder_unb)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Level order values myBST_unb: " << std::endl;
    for (auto& val : vals_level_order_unb)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Inorder values myBST_b: " << std::endl;
    for (auto& val : vals_inorder_b)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Preorder values myBST_b: " << std::endl;
    for (auto& val : vals_preorder_b)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Postorder values myBST_b: " << std::endl;
    for (auto& val : vals_postorder_b)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Level order values myBST_b: " << std::endl;
    for (auto& val : vals_level_order_b)
        std::cout << val << " ";
    std::cout << std::endl;


    // ---------------------------------------
    std::cout << "--------------------------\n";
    std::cout << "Remove nodes" << std::endl;

    BinarySearchTree myBST;
    std::vector<int> values {1, 2, 3, 4, 5, 6, 7, 8, 9};
    myBST.build_from_vector_balanced(values);

    std::cout << "Max value: " << myBST.max_val() << std::endl;
    std::cout << "Min value: " << myBST.min_val() << std::endl;
    std::cout << "Contains 5: " << myBST.contains(5) << std::endl;
    std::cout << "Contains 15: " << myBST.contains(15) << std::endl;

    std::cout << "Before removing nodes" << std::endl;
    std::cout << "myBST size: " << myBST.size() << std::endl;
    std::cout << "myBST empty? " << myBST.empty() << std::endl;
    std::vector<int> vals_inorder = myBST.get_inorder_vals();
    std::cout << "Inorder values: " << std::endl;
    for (auto& val : vals_inorder)
        std::cout << val << " ";
    std::cout << std::endl;

    myBST.remove_node(9);
    myBST.remove_node(5);
    myBST.remove_node(2);
    myBST.remove_node(1);
    myBST.remove_node(1);

    std::cout << "Removed 9, 5, 2, 1, 1" << std::endl;
    std::cout << "myBST size: " << myBST.size() << std::endl;
    std::cout << "myBST empty? " << myBST.empty() << std::endl;
    vals_inorder = myBST.get_inorder_vals();
    std::cout << "Inorder values: " << std::endl;
    for (auto& val : vals_inorder)
        std::cout << val << " ";
    std::cout << std::endl;

    myBST.remove_node(80);
    myBST.remove_node(2);
    myBST.remove_node(3);
    myBST.remove_node(4);
    myBST.remove_node(6);
    myBST.remove_node(7);
    myBST.remove_node(8);

    std::cout << "Removed 80, 2, 3, 4, 6, 7, 8" << std::endl;
    std::cout << "myBST size: " << myBST.size() << std::endl;
    std::cout << "myBST empty? " << myBST.empty() << std::endl;


    // ---------------------------------------
    std::cout << "--------------------------\n";
    std::cout << "Insert nodes" << std::endl;
    myBST.insert_node(10);
    myBST.insert_node(50);
    myBST.insert_node(20);
    myBST.insert_node(5);

    std::cout << "Inserted 10, 50, 20, 5" << std::endl;
    std::cout << "myBST size: " << myBST.size() << std::endl;
    std::cout << "myBST empty? " << myBST.empty() << std::endl;
    vals_inorder = myBST.get_inorder_vals();
    std::cout << "Inorder values: " << std::endl;
    for (auto& val : vals_inorder)
        std::cout << val << " ";
    std::cout << std::endl;



    // ---------------------------------------
    std::cout << "--------------------------\n";
    std::cout << "Copy constructor" << std::endl;
    BinarySearchTree myBST_orig;

    myBST_orig.build_from_vector_balanced(values);
    BinarySearchTree myBST_copy = myBST_orig;

    myBST_orig.insert_node(15);
    myBST_copy.insert_node(12);

    std::vector<int> vals_inorder_orig = myBST_orig.get_inorder_vals();
    std::vector<int> vals_inorder_copy = myBST_copy.get_inorder_vals();

    std::cout << "Inorder values myBST_orig: " << std::endl;
    for (auto& val : vals_inorder_orig)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Inorder values myBST_copy: " << std::endl;
    for (auto& val : vals_inorder_copy)
        std::cout << val << " ";
    std::cout << std::endl;


    // ---------------------------------------
    std::cout << "--------------------------\n";
    std::cout << "Copy assignment operator" << std::endl;
    // Not really sure how to test this

    BinarySearchTree myBST_orig_assign;
    std::vector<int> values1 {1, 2, 3, 4, 5};
    myBST_orig_assign.build_from_vector_balanced(values1);
    BinarySearchTree myBST_copy_assign;
    std::vector<int> values2 {6, 7, 8, 9};
    myBST_copy_assign.build_from_vector_balanced(values2);

    std::vector<int> vals_inorder_orig_assign = myBST_orig_assign.get_inorder_vals();
    std::vector<int> vals_inorder_copy_assign = myBST_copy_assign.get_inorder_vals();

    std::cout << "Inorder values before assign: myBST_orig_assign: " << std::endl;
    for (auto& val : vals_inorder_orig_assign)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Inorder values before assign: myBST_copy_assign: " << std::endl;
    for (auto& val : vals_inorder_copy_assign)
        std::cout << val << " ";
    std::cout << std::endl;
    myBST_orig_assign = myBST_copy_assign;

    vals_inorder_orig_assign = myBST_orig_assign.get_inorder_vals();
    vals_inorder_copy_assign = myBST_copy_assign.get_inorder_vals();

    std::cout << "Inorder values after assign: myBST_orig_assign: " << std::endl;
    for (auto& val : vals_inorder_orig_assign)
        std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Inorder values after assign: myBST_copy_assign: " << std::endl;
    for (auto& val : vals_inorder_copy_assign)
        std::cout << val << " ";
    std::cout << std::endl;


    // ---------------------------------------
    std::cout << "--------------------------\n";
    std::cout << "Move constructor" << std::endl;

    BinarySearchTree myBST_orig_move;
    myBST_orig_move.build_from_vector_balanced(values);
    std::cout << "myBST_orig_move before move: empty? " << myBST_orig_move.empty() << "\n";
    BinarySearchTree myBST_target_move(std::move(myBST_orig_move));

    std::cout << "myBST_orig_move after move: empty? " << myBST_orig_move.empty() << "\n";
    std::cout << "myBST_target_move after move: empty? " << myBST_target_move.empty() << "\n";


    // ---------------------------------------
    std::cout << "--------------------------\n";
    std::cout << "Move assignment operator" << std::endl;

    BinarySearchTree myBST_orig_move_assign;
    myBST_orig_move_assign.build_from_vector_balanced(values1);
    BinarySearchTree myBST_target_move_assign;
    myBST_target_move_assign.build_from_vector_balanced(values2);

    std::cout << "myBST_orig_move_assign before move: empty? " << myBST_orig_move_assign.empty() << "\n";
    std::cout << "myBST_target_move_assign before move: empty? " << myBST_target_move_assign.empty() << "\n";

    myBST_target_move_assign = std::move(myBST_orig_move_assign);

    std::cout << "myBST_orig_move_assign after move: empty? " << myBST_orig_move_assign.empty() << "\n";
    std::cout << "myBST_target_move_assign after move: empty? " << myBST_target_move_assign.empty() << "\n";

}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ It would help us review the code if you included the testing code as well. \$\endgroup\$ Commented May 18, 2020 at 15:47
  • 1
    \$\begingroup\$ Good point, @pacmaninbw. I added the main.cpp code. \$\endgroup\$ Commented May 18, 2020 at 17:43
  • 2
    \$\begingroup\$ For rule-of-5, since you don't have any resources to explicitly release, you don't need a specialized destructor. However, the rule applies for this: make your intent clear by declaring it default, so the next person looking at your code knows that you didn't just miss it. \$\endgroup\$ Commented May 18, 2020 at 18:40
  • \$\begingroup\$ @Oppen, thanks! What about Node struct? Should I also declare destructor as default? \$\endgroup\$ Commented May 19, 2020 at 16:29
  • 1
    \$\begingroup\$ I'm generally in favor of being explicit, but I don't know what's considered "idiomatic" in this case, as it's not part of the rule-of-5. I think I would mark it default. \$\endgroup\$ Commented May 19, 2020 at 16:51

1 Answer 1

Reset to default
3
+50
\$\begingroup\$

This is too long for me to review thoroughly, but on a cursory glance (I'll just go go top to bottom):

  1. #include <iostream> is unneeded
  2. There is no point in calling clear in the destructor. This class should not have any code in the destructor at all. The smart pointers are meant to clean up nicely.
  3. There is no point passing int as a const reference
  4. You are too attached to vectors. It may be fine for the specific task, but for a more library-oriented class this would be a burden. But even if you stick to vectors, having a type alias would help readability and maintanability
  5. Node* find_min_node(const std::unique_ptr& curr_node) const; It should really be const Node*
  6. BinarySearchTree::BinarySearchTree(const BinarySearchTree& other_tree) { if (other_tree.tree_size == 0) return; this constructor does not initialize the fields. Which is quite strange because the default constructor does.
  7. std::vector<int>::iterator it_e = values.end() - 1; This is incorrect. If values is empty it will give you an invalid iterator. You check it with < later in the code, but this is not correct C++, you can only compare iterators from the same container, which are [begin, end+1]. It will probably work just because vector iterators are likely to be just numbers, but it can break with any library or compiler update.
  8. min_val will break horribly if the tree is empty
  9. Your insert code suggests that the tree can not contain duplicate values. It is totally fine, but for me it would be unexpected from a class with such a generic name.
\$\endgroup\$
2
  • \$\begingroup\$ Thank you for your reply, I have a couple of follow up questions: 4. What would you use instead of vectors? 5. Should it be const Node* const then, as I don't want to modify neither pointer itself nor its contents? 7. So, if I want to do binary search in a vector, should I use indexes instead of iterators or could I still use iterators, but in a different way? \$\endgroup\$ Commented May 20, 2020 at 20:30
  • 1
    \$\begingroup\$ 4.Ideally you should use iterators, the same principle as the STL does. 5. Yo can not modify the pointer itself, you are returning a copy of the pointer, so second const is unnecessary. 7. You can play with iterator_categories. If your iterator is random-access you can use binary search. Or you can just use operator + for example, in that case a non-random-access iterator won't compile. \$\endgroup\$ Commented May 21, 2020 at 6:04

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.