BST.cpp

Go to the documentation of this file.

 
#include "BST.h"
#include "Stack.h"
#include "Queue.h"
#include <iostream>

BST::BST() : root(nullptr) {}

BST::~BST() {
    destroyTree();
}

void BST::insert(int value) {
    Node* newNode = new Node(value);
 
    // Special case: empty tree
    if (!root) {
        root = newNode;
        return;
    }
 
    Node* current = root;
    Node* parent = nullptr;
 
    // Traverse the tree to find the insertion point
    while (current) {
        parent = current;
 
        if (value < current->getValue())
            current = current->getLeft();
        else if (value > current->getValue())
            current = current->getRight();
        else {
            // Duplicate value detected; discard new node
            delete newNode;
            return;
        }
    }
 
    // Attach the new node to its parent
    if (value < parent->getValue())
        parent->setLeft(newNode);
    else
        parent->setRight(newNode);
}

bool BST::search(int value) const {
    Node* current = root;
 
    while (current) {
        if (value == current->getValue())
            return true;
        else if (value < current->getValue())
            current = current->getLeft();
        else
            current = current->getRight();
    }
 
    return false;
}

void BST::inorder() const {
    if (!root) return;
 
    Stack s;
    Node* current = root;
 
    while (current || !s.isEmpty()) {
        while (current) {
            s.push(current);
            current = current->getLeft();
        }
 
        current = s.pop();
        std::cout << current->getValue() << " ";
        current = current->getRight();
    }
 
    std::cout << std::endl;
}

void BST::levelOrder() const {
    if (!root) return;
 
    Queue q;
    q.enqueue(root);
 
    while (!q.isEmpty()) {
        Node* current = q.dequeue();
        std::cout << current->getValue() << " ";
 
        if (current->getLeft())
            q.enqueue(current->getLeft());
        if (current->getRight())
            q.enqueue(current->getRight());
    }
 
    std::cout << std::endl;
}

bool BST::remove(int value) {
    Node* parent = nullptr;
    Node* current = root;
 
    // Locate the node to delete
    while (current && current->getValue() != value) {
        parent = current;
        if (value < current->getValue())
            current = current->getLeft();
        else
            current = current->getRight();
    }
 
    if (!current)
        return false; // Value not found
 
    // ------------------------------------------------------------
    // Case 1: Node has no children (leaf)
    // ------------------------------------------------------------
    if (!current->getLeft() && !current->getRight()) {
        if (current == root)
            root = nullptr;
        else if (parent->getLeft() == current)
            parent->setLeft(nullptr);
        else
            parent->setRight(nullptr);
 
        delete current;
    }
 
    // ------------------------------------------------------------
    // Case 2: Node has exactly one child
    // ------------------------------------------------------------
    else if (!current->getLeft() || !current->getRight()) {
        Node* child = current->getLeft()
            ? current->getLeft()
            : current->getRight();
 
        if (current == root)
            root = child;
        else if (parent->getLeft() == current)
            parent->setLeft(child);
        else
            parent->setRight(child);
 
        delete current;
    }
 
    // ------------------------------------------------------------
    // Case 3: Node has two children
    // ------------------------------------------------------------
    else {
        // Find inorder successor (leftmost node in right subtree)
        Node* succParent = current;
        Node* successor = current->getRight();
 
        while (successor->getLeft()) {
            succParent = successor;
            successor = successor->getLeft();
        }
 
        // Replace current node's value with successor's value
        current->setValue(successor->getValue());
 
        // Remove successor node (which has at most one child)
        Node* child = successor->getRight();
 
        if (succParent->getLeft() == successor)
            succParent->setLeft(child);
        else
            succParent->setRight(child);
 
        delete successor;
    }
 
    return true;
}

void BST::destroyTree() {
    if (!root) return;
 
    Stack s;
    s.push(root);
 
    while (!s.isEmpty()) {
        Node* current = s.pop();
 
        if (current->getLeft())
            s.push(current->getLeft());
        if (current->getRight())
            s.push(current->getRight());
 
        delete current;
    }
 
    root = nullptr;
}