Binary Search Tree search, insert, and deletion operations with unit tests.

bst.cpp

#define CATCH_CONFIG_MAIN
#include "catch.hpp"
#include <vector>

using namespace std;

struct Node {
    int value;
    Node *left;
    Node *right;
};

/* recursive search */
Node* SearchRecursive(Node* root, int value) {
    if (root) {
        if (root->value == value) return root;
        else if (value <= root->value) return SearchRecursive(root->left, value);
        else return SearchRecursive(root->right, value);
    }
    return NULL;
}

/* iterative search */
Node* SearchIterative(Node* root, int value) {
    if (root) {
        vector<Node*> to_visit;
        to_visit.push_back(root);
        while (to_visit.size() > 0) {
            Node* next = to_visit.back();
            to_visit.pop_back();

            if (next->value == value) return next;
            else if (next->left && value <= next->value) to_visit.push_back(next->left);
            else if (next->right && value > next->value) to_visit.push_back(next->right);
        }
    }
    return NULL;
}

/* recursive insert */
Node* InsertRecursive(Node *root, int value) {
    if (!root) {
        root = new Node();
        root->value = value;
    }
    else if (value <= root->value) root->left = InsertRecursive(root->left, value);
    else root->right = InsertRecursive(root->right, value);
    return root;
}

/* iterative insert */
Node* InsertIterative(Node *root, int value) {
    if (!root) {
        root = new Node();
        root->value = value;
        return root;
    }

    vector<Node*> to_visit;
    to_visit.push_back(root);
    Node *next = root;

    while (to_visit.size() > 0) {
        next = to_visit.back();
        to_visit.pop_back();

        if (value <= next->value) {
            if (next->left) to_visit.push_back(next->left);
            else {
                next->left = new Node();
                next->left->value = value;
            }
        }
        else {
            if (next->right) to_visit.push_back(next->right);
            else {
                next->right = new Node();
                next->right->value = value;
            }
        }
    }

    return root;
}


/* find the minimum value in a tree */
Node* MinNode(Node* root) {
  while (root->left) {
    root = root->left;
  }
  return root;
}

/* recursive removal */
Node* Remove(Node* root, int value) {
    // step 1: find the element to be removed
    if (root) {
        if (value < root->value) root->left = Remove(root->left, value);
        else if (value > root->value) root->right = Remove(root->right, value);
        else {
            // here we found the element to remove.

            // Easy case - element is a leaf node.
            if (!root->left && !root->right) {
                delete root;
                root = NULL;
            }

            // Easy case - element to delete has a subtree on the right.
            else if (!root->left) {
                Node* temp = root;
                root = root->right;
                delete temp;
            }

            // Easy case - element to delete has a subtree on the left.
            else if (!root->right) {
                Node* temp = root;
                root = root->left;
                delete temp;
            }

            // Tricky case - element to delete has two subtrees.
            else {
                /* Find either the minimum element in the right subtree
                   or the maximum element in the left subtree. */
                Node* min = MinNode(root->right);
                root->value = min->value;
                // The problem has now been reduced to an easy case.
                root->right = Remove(root->right, min->value);
            }
        }
    }
    return root;
}


TEST_CASE("BST operations", "[Insert]") {

    REQUIRE(InsertRecursive(NULL, 0)->value == 0);
    REQUIRE(InsertRecursive(NULL, 1)->value == 1);

    SECTION("Nodes get InsertRecursive'ed into right spot") {
        Node *root = NULL;
        root = InsertRecursive(root, 5);

        REQUIRE(root->value == 5);

        root = InsertRecursive(root, 4);
        root = InsertRecursive(root, 6);

        REQUIRE(root->left->value == 4);
        REQUIRE(root->right->value == 6);

        root = InsertRecursive(root, 10);
        root = InsertRecursive(root, 7);
        REQUIRE(root->right->right->value == 10);
        REQUIRE(root->right->right->left->value == 7);
    }

    SECTION("Nodes get InsertIteratively'ed into right spot") {
        Node *root = NULL;
        root = InsertIterative(root, 5);

        REQUIRE(root->value == 5);

        root = InsertIterative(root, 4);
        root = InsertIterative(root, 6);

        REQUIRE(root->left->value == 4);
        REQUIRE(root->right->value == 6);

        root = InsertIterative(root, 10);
        root = InsertIterative(root, 7);
        REQUIRE(root->right->right->value == 10);
        REQUIRE(root->right->right->left->value == 7);
    }

    SECTION("Searching") {
        Node *root = NULL;
        root = InsertIterative(root, 10);
        root = InsertIterative(root, 20);
        root = InsertIterative(root, 0);
        root = InsertRecursive(root, 7);
        root = InsertRecursive(root, 78);

        REQUIRE(SearchRecursive(root, 10)->value == 10);
        REQUIRE(SearchRecursive(root, 20)->value == 20);
        REQUIRE(SearchRecursive(root, 0)->value == 0);
        REQUIRE(SearchRecursive(root, 78)->value == 78);
        REQUIRE(SearchRecursive(root, 7)->value == 7);
        REQUIRE(SearchRecursive(root, 50) == NULL);
        REQUIRE(SearchRecursive(NULL, 50) == NULL);

        REQUIRE(SearchIterative(root, 10)->value == 10);
        REQUIRE(SearchIterative(root, 20)->value == 20);
        REQUIRE(SearchIterative(root, 0)->value == 0);
        REQUIRE(SearchIterative(root, 78)->value == 78);
        REQUIRE(SearchIterative(root, 7)->value == 7);
        REQUIRE(SearchIterative(root, 50) == NULL);
        REQUIRE(SearchIterative(NULL, 50) == NULL);
    }

    SECTION("Removal") {
        Node* root = NULL;
        root = InsertIterative(root, 5);
        root = InsertIterative(root, 1);
        root = InsertIterative(root, 9);
        root = InsertIterative(root, 10);
        root = InsertIterative(root, 0);

        REQUIRE(MinNode(root)->value == 0);

        root = Remove(root, 5);
        REQUIRE(SearchRecursive(root, 5) == NULL);

        root = Remove(root, 0);
        REQUIRE(SearchRecursive(root, 0) == NULL);

        root = Remove(root, 1);
        REQUIRE(SearchRecursive(root, 1) == NULL);

    }

}

catch.hpp can be found here https://github.com/philsquared/Catch