intbst.cpp

// intbst.cpp
// Implements class IntBST
// Harsha Malaviya 1/25/26

#include "intbst.h"

#include <iostream>
using std::cout;

// constructor sets up empty tree
IntBST::IntBST() {
    this->root = nullptr;
}

// destructor deletes all nodes
IntBST::~IntBST() {
    clear(root);
}

// recursive helper for destructor
void IntBST::clear(Node *n) {
    if(!n) return;
    clear(n->left);
    clear(n->right);
    delete n;
}

// insert value in tree; return false if duplicate
bool IntBST::insert(int value) {
    if(!root){
        root = new Node(value);
        return true;
    }
    return insert(value,root);; // REPLACE THIS NON-SOLUTION
}

// recursive helper for insert (assumes n is never 0)
bool IntBST::insert(int value, Node *n) {
    if(!n) return false;
    if (value==n->info) return false;
    if (value>n->info){
        if(!n->right){
            n->right = new IntBST::Node(value);
            return true;
        }
        return insert(value,n->right);
    } else{
        if (!n->left)
        {
            n->left = new IntBST::Node(value);
            return true;
        }
        return insert(value,n->left);
    }
}

// print tree data pre-order
void IntBST::printPreOrder() const {
    printPreOrder(root);
    //cout << "\n";
}

// recursive helper for printPreOrder()
void IntBST::printPreOrder(Node *n) const {
    if(!n) return;
    cout << n->info << " ";
    printPreOrder(n->left);
    printPreOrder(n->right);
}

// print tree data in-order, with helper
void IntBST::printInOrder() const {
    printInOrder(root);
    //cout << "\n";
}
void IntBST::printInOrder(Node *n) const {
    if(!n) return;
    printInOrder(n->left);
    cout << n->info << " ";
    printInOrder(n->right);
}

// prints tree data post-order, with helper
void IntBST::printPostOrder() const {
    printPostOrder(root);
    //cout << "\n";
}

void IntBST::printPostOrder(Node *n) const {
    if(!n) return;
    printPostOrder(n->left);
    printPostOrder(n->right);
    cout << n->info << " ";
}

// return sum of values in tree
int IntBST::sum() const {
    return sum(root);
}

// recursive helper for sum
int IntBST::sum(Node *n) const {
    if(!n) return 0;
    return n->info + sum(n->left) + sum(n->right);
}

// return count of values
int IntBST::count() const {
    return count(root);
}

// recursive helper for count
int IntBST::count(Node *n) const {
    if(!n) return 0;
    return 1 + count(n->left) + count(n->right);
}

// IMPLEMENT THIS FIRST: returns the node for a given value or NULL if none exists
// Parameters:
// int value: the value to be found
// Node* n: the node to start with (for a recursive call)
// Whenever you call this method from somewhere else, pass it
// the root node as "n"
IntBST::Node* IntBST::getNodeFor(int value, Node* n) const{
    if(!n) return NULL;
    if(n->info == value) return n;
    if(n->info>value) return getNodeFor(value,n->left);
    else return getNodeFor(value,n->right);
}

// returns true if value is in the tree; false if not
bool IntBST::contains(int value) const {
    return (getNodeFor(value,root)!=nullptr);
}

// returns the Node containing the predecessor of the given value
IntBST::Node* IntBST::getPredecessorNode(int value) const {
    Node* node = getNodeFor(value, root);
    if (!node) return nullptr;

    if (node->left) {
        Node* p = node->left;
        while (p->right) p = p->right;
        return p;
    }

    Node* curr = root;
    Node* pred = nullptr;
    while (curr) {
        if (value > curr->info) {
            pred = curr;
            curr = curr->right;
        }
        else if (value < curr->info) {
            curr = curr->left;
        }
        else break;
    }
    return pred;
}

// returns the predecessor value of the given value or 0 if there is none
int IntBST::getPredecessor(int value) const{
    Node* pred = getPredecessorNode(value);
    if (pred == nullptr)
        return 0;
    return pred->info;
}

// returns the Node containing the successor of the given value
IntBST::Node* IntBST::getSuccessorNode(int value) const {
    Node* node = getNodeFor(value, root);
    if (!node) return nullptr;

    if (node->right) {
        Node* s = node->right;
        while (s->left) s = s->left;
        return s;
    }

    Node* curr = root;
    Node* succ = nullptr;
    while (curr) {
        if (value < curr->info) {
            succ = curr;
            curr = curr->left;
        }
        else if (value > curr->info) {
            curr = curr->right;
        }
        else break;
    }
    return succ;
}


// returns the successor value of the given value or 0 if there is none
int IntBST::getSuccessor(int value) const {
    Node* succ = getSuccessorNode(value);
    if (succ == nullptr)
        return 0;
    return succ->info;
}


// deletes the Node containing the given value from the tree
// returns true if the node exist and was deleted or false if the node does not exist
bool IntBST::remove(int value) {
    Node* curr = root;
    Node* parent = nullptr;

    while (curr && curr->info != value) {
        parent = curr;
        curr = (value < curr->info) ? curr->left : curr->right;
    }

    if (!curr) return false;

    if (curr->left && curr->right) {
        Node* succ = curr->right;
        Node* succParent = curr;

        while (succ->left) {
            succParent = succ;
            succ = succ->left;
        }

        curr->info = succ->info;
        parent = succParent;
        curr = succ;
    }

    Node* next = curr->left ? curr->left : curr->right;

    if (!parent) {
        root = next;
    } else if (parent->left == curr) {
        parent->left = next;
    } else {
        parent->right = next;
    }

    delete curr;
    return true;
}