Untitled

// intbst.cpp
// Implements class IntBST
// Tuan Le, 1/27/2023


#include "intbst.h"


#include <iostream>
#include <stack>
using std::cout;


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


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


// recursive helper for destructor
void IntBST::clear(Node *n) {
   if (!n) return;
   // Post-order search
   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;
   }
   else return insert(value, root);
}


// recursive helper for insert (assumes n is never 0)
bool IntBST::insert(int value, Node *n) {
   // If the value is a duplicate, return false
   if (n->info == value) {
       return false;
   }
   // If the value is greater than the current node info, traverse right
   else if (n->info < value) {
       // If there is no right child node, create a new child node with the value
       if (!n->right) {
           n->right = new Node(value);
           n->right->parent = n;
           return true;
       }
       // Traverse right
       else return insert(value, n->right);
   }
   // If the value is lesser than the current node info, traverse left
   else {
       if (!n->left) {
           // If there is no left child node, create a new child node with the value
           n->left = new Node(value);
           n->left->parent = n;
           return true;
       }
       // Traverse left
       else return insert(value, n->left);
   }
}


// print tree data pre-order
void IntBST::printPreOrder() const {
   if (!root) {
       return;
   }
   printPreOrder(root);
}
// 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 {
   if (!root) return;
   printInOrder(root);
}
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);
}


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 {
   if (!root) return 0;
   return sum(root);
}


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


// return count of values
int IntBST::count() const {
   // Iterative Method:
   if (!root) return 0;
   stack<Node *> treeStack;
   Node* currNode = root;
   int count = 0;
   while (!treeStack.empty() || currNode) {
       if (currNode) {
           count++;
           if (currNode->right)
               treeStack.push(currNode->right);
           currNode = currNode->left;
       }
       else {
           currNode = treeStack.top();
           treeStack.pop();
       }
   }
   return count;


   // Recursive Method:
   // if (!root) return 0;
   // return count(root);
}


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


// 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{
   // Base Case: Returns NULL if the value isn't in the tree
   if (!n) return NULL;
   // 2nd Base Case: Returns the Node if the value is found
   if (n->info == value) return n;
   // Traverses right if the value is greater than the current node
   else if (n->info < value) return getNodeFor(value, n->right);
   // Else, traverses left
   else return getNodeFor(value, n->left);
}


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


// returns the Node containing the predecessor of the given value
IntBST::Node* IntBST::getPredecessorNode(int value) const{
   // Checks if the tree is empty or if the value exists in the tree
   if (!root || !contains(value)) return 0;
   Node* node = getNodeFor(value, root);
   // If the left child node doesn't exist, check if the parent nodes exists and is lesser than the value,
   // if so return the parent node, else return 0
   if (!node->left) {
       while(node->parent) {
           if (node->parent->info < value) return node->parent;
           node = node->parent;
       }
       return 0;
   }
   // If the left node exists, traverse right and go as far left as possible
   else {
       node = node->left;
       while(node->right) {
           node = node->right;
       }
   }
   return node; // REPLACE THIS NON-SOLUTION
}


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


// returns the Node containing the successor of the given value
IntBST::Node* IntBST::getSuccessorNode(int value) const{
   // Checks if the tree is empty or if the value exists in the tree
   if (!root || !contains(value)) return 0;
   Node* node = getNodeFor(value, root);
   // If the right child node doesn't exist, check if the parent node exists and is lesser than the value,
   // return the parent node if it exists or return 0
   if (!node->right) {
       while (node->parent) {
           if (node->parent->info > value) return node->parent;
           node = node->parent;
       }
       return 0;
   }
   // If the right node exists, traverse left and go as far left as possible
   else {
       node = node->right;
       while (node->left) {
           node = node->left;
       }
   }
   return node;
}


// returns the successor value of the given value or 0 if there is none
int IntBST::getSuccessor(int value) const{
   if (!getSuccessorNode(value)) return 0;
   else return getSuccessorNode(value)->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){
   if (!root || !contains(value)) return false;
   Node* node = getNodeFor(value, root);
   // Checks if the node is a leaf node
   if (!node->right && !node->left) {
       // If the node has no parents, it is the root node, so create an empty tree
       if (!node->parent) {
           root = 0;
       }
       // If the node is left of the parent, reasign the parent's left child to 0
       else if (node->parent->left == node) {
           node->parent->left = 0;
       }
       // If the node is right of the parent, reasign the parent's right child to 0
       else if (node->parent->right == node) {
           node->parent->right = 0;
       }
   }
   // Checks if the node has only has a left child
   else if (!node->right && node->left) {
       // If the node has no parent, reasign the root and child's parent
       if (!node->parent) {
           root = node->left;
           node->left->parent = 0;
       }
       // If the node is left of the parent, reasign the parent's left child and the child's parent
       else if (node->parent->left == node) {
           node->parent->left = node->left;
           node->left->parent = node->parent;
       }
       // If the node is right of the parent, reasign the parent's right child and the child's parent
       else if (node->parent->right == node) {
           node->parent->right = node->left;
           node->left->parent = node->parent;
       }
   }
   // Checks if the node has only has a right child, mostly the same as the conditional above
   else if (!node->left && node->right) {
       if (!node->parent) {
           root = node->right;
           node->right->parent = 0;
       }
       else if (node->parent->left == node) {
           node->parent->left = node->right;
           node->right->parent = node->parent;
       }
       else if (node->parent->right == node) {
           node->parent->right = node->right;
           node->right->parent = node->parent;
       }
   }
   // If the node has two children, then find the successor and reasign it
   else {
       Node* successor = getSuccessorNode(value);
      
       // If the successor's parent is the node itself, replace the node with the successor
       if (successor->parent == node) {
           successor->parent = node->parent;
           node->left->parent = successor;
           successor->left = node->left;
       }
       else {
           // If the successor has a child, reasign it
           if (successor->right) {
               successor->right->parent = successor->parent;
           }
           successor->parent->left = successor->right;
           // Set the successor's parent to the node's parent
           successor->parent = node->parent;
           // Replace the node with the successor
           node->left->parent = successor;
           node->right->parent = successor;
           successor->left = node->left;
           successor->right = node->right;
       }

       // If the node has parents, reasign the child parent to the successor
       if (node->parent) {
           if (node->parent->left == node)
               node->parent->left = successor;
           else
               node->parent->right = successor;
       }
       else {
           root = successor;
       }
   }
   delete node;
   return true;
}