cis22c/05-trees/BinarySearchTree.h

// Binary Search Tree ADT
// Created by Iurii Tatishchev
// Modified by: Iurii Tatishchev

#ifndef _BINARY_SEARCH_TREE
#define _BINARY_SEARCH_TREE

#include "BinaryTree.h"

template<class ItemType>
class BinarySearchTree : public BinaryTree<ItemType> {
public:
    // insert a node at the correct location
    bool insert(const ItemType &item);

    // remove a node if found
    // bool remove(const ItemType &item);
    // find a target node
    bool search(const ItemType &target, ItemType &returnedItem) const;

    // find the smallest node
    bool findSmallest(ItemType &returnedItem) const;

    // find the largest node
    bool findLargest(ItemType &returnedItem) const;

private:
    // internal insert node: insert newNode in nodePtr subtree
    BinaryNode<ItemType> *_insert(BinaryNode<ItemType> *nodePtr, BinaryNode<ItemType> *newNode);

    // search for target node
    BinaryNode<ItemType> *_search(BinaryNode<ItemType> *treePtr, const ItemType &target) const;

    // find the smallest node
    BinaryNode<ItemType> *_findSmallest(BinaryNode<ItemType> *nodePtr, ItemType &smallest) const;

    // find the largest node
    BinaryNode<ItemType> *_findLargest(BinaryNode<ItemType> *nodePtr, ItemType &smallest) const;

    // internal remove node: locate and delete target node under nodePtr subtree
    // BinaryNode<ItemType>* _remove(BinaryNode<ItemType>* nodePtr, const ItemType target, bool &success);

    // delete target node from tree, called by internal remove node
    // BinaryNode<ItemType>* _removeNode(BinaryNode<ItemType>* targetNodePtr);

    // remove the leftmost node in the left subtree of nodePtr
    // BinaryNode<ItemType>* _removeLeftmostNode(BinaryNode<ItemType>* nodePtr, ItemType &successor);

};

///////////////////////// public function definitions ///////////////////////////
// Wrapper for _insert - Inserting items within a tree
template<class ItemType>
bool BinarySearchTree<ItemType>::insert(const ItemType &newEntry) {
    auto *newNodePtr = new BinaryNode<ItemType>(newEntry);
    this->rootPtr = _insert(this->rootPtr, newNodePtr);
    this->count++;
    return true;
}

// Finding the smallest, which is the leftmost leaf (wrapper function)
template<class ItemType>
bool BinarySearchTree<ItemType>::findSmallest(ItemType &returnedItem) const {
    BinaryNode<ItemType> *temp = nullptr;
    temp = _findSmallest(this->rootPtr, returnedItem);
    return temp != nullptr;
}

// Finding the largest, which is the rightmost leaf (wrapper function)
template<class ItemType>
bool BinarySearchTree<ItemType>::findLargest(ItemType &returnedItem) const {
    BinaryNode<ItemType> *temp = nullptr;
    temp = _findLargest(this->rootPtr, returnedItem);
    return temp != nullptr;
}

// Wrapper for _search
// - it calls the private _search function that returns a Node pointer or NULL
// - if found, it copies data from that node and sends it back to the caller
//   via the output parameter, and returns true, otherwise it returns false.
template<class ItemType>
bool BinarySearchTree<ItemType>::search(const ItemType &anEntry, ItemType &returnedItem) const {
    BinaryNode<ItemType> *temp = nullptr;
    temp = _search(this->rootPtr, anEntry);

    if (temp != nullptr) {
        returnedItem = temp->getItem();
        return true;
    }
    return false;
}


//////////////////////////// private functions ////////////////////////////////////////////

// Recursive implementation of the insert operation
template<class ItemType>
BinaryNode<ItemType> *BinarySearchTree<ItemType>::_insert(BinaryNode<ItemType> *nodePtr,
                                                          BinaryNode<ItemType> *newNodePtr) {
    // Base case: tree is empty
    if (nodePtr == nullptr) return newNodePtr;

    // Inserting larger item to the right:
    if (nodePtr->getItem() < newNodePtr->getItem()) {
        // Recurse if right child is not null
        if (nodePtr->getRightPtr() != nullptr)
            _insert(nodePtr->getRightPtr(), newNodePtr);
            // Otherwise, insert the new node
        else nodePtr->setRightPtr(newNodePtr);
    }
        // Inserting smaller item to the left:
    else {
        // Recurse if left child is not null
        if (nodePtr->getLeftPtr() != nullptr)
            _insert(nodePtr->getLeftPtr(), newNodePtr);
            // Otherwise, insert the new node
        else nodePtr->setLeftPtr(newNodePtr);
    }

    // Return the root node
    return nodePtr;
}

// Implementation to find the smallest: recursive
template<class ItemType>
BinaryNode<ItemType> *
BinarySearchTree<ItemType>::_findSmallest(BinaryNode<ItemType> *nodePtr, ItemType &smallest) const {
    if (nodePtr->getLeftPtr() == nullptr) {
        smallest = nodePtr->getItem();
        return nodePtr;
    }
    return _findSmallest(nodePtr->getLeftPtr(), smallest);
}

// Implementation to find the largest: recursive
template<class ItemType>
BinaryNode<ItemType> *BinarySearchTree<ItemType>::_findLargest(BinaryNode<ItemType> *nodePtr, ItemType &biggest) const {
    if (nodePtr->getRightPtr() == nullptr) {
        biggest = nodePtr->getItem();
        return nodePtr;
    }
    return _findLargest(nodePtr->getRightPtr(), biggest);
}

// Recursive implementation of the search operation
// - return NULL if target not found, otherwise
// - returns a pointer to the node that matched the target
template<class ItemType>
BinaryNode<ItemType> *BinarySearchTree<ItemType>::_search(BinaryNode<ItemType> *nodePtr,
                                                          const ItemType &target) const {
    // Two base cases: root is NULL or target is found
    if (nodePtr == nullptr) return nullptr;
    if (nodePtr->getItem() == target) return nodePtr;

    // Recursive cases, search either left or right subtree based on the target
    if (target < nodePtr->getItem()) return _search(nodePtr->getLeftPtr(), target);
    if (target > nodePtr->getItem()) return _search(nodePtr->getRightPtr(), target);

    // To prevent compiler warning
    return nullptr;
}

#endif