avl tree

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Node{		// Class creates new node objects
public:
    Node();
    int value;
	Node* left;
    Node* right;
    ~Node();
};

class AVLTree{	// class creates new tree
public:
    Node *root;								// points to root of the tree
	bool first;								// used for spacing in output
	std::vector<Node*> path;
	AVLTree();
	void insert(int number);				// inserts number into tree - does nothing if already in tree
	void remove(int number);				// removes number from tree- does nothing if not in tree
	bool isEmpty();							// Checks if 'root' points to NULL
	void traverse(std::string method);		// Outputs using specified method
	void postOrder(Node* current);			// different traversing methods
	void preOrder(Node* current);			// " "
	void inOrder(Node* current);			// " "
	int height(Node* current);				// returns height of subtree
	int levelCount(Node* current, int total, int level);
	int heightDiff(Node* current);			// returns difference in height of two subtrees of a given node
	void balance();						// desides on the rotation method
	void leftLeft(Node* current, Node* parent);						// different rotation methods
	void rightRight(Node* current, Node* Parent);						// " "
    ~AVLTree();
};

AVLTree::AVLTree(){
	root = NULL;
	first = true;
}

Node::Node(){
    left = NULL;        //initialtes new node pointer to NULL and digit to 0
	right = NULL;
	value = 0;
}

bool AVLTree::isEmpty(){
	return root == NULL;
}

void AVLTree::balance(){
	Node* current = NULL;
	Node* parent = NULL;
	for(int i = 0 ; i < path.size(); i++){
		current = path[i];
		if(i > 0){
			parent = path[i-1];
		}
		int bal = heightDiff(current);
		if(bal > 1){
			if(heightDiff(current->left) >= 0){
				// std::cout << "left" << current->value << std::endl;
				leftLeft(current, parent);
			}else{
				// std::cout << "left right" << std::endl;
				rightRight(current->left, current);
				leftLeft(current, parent);
			}
		}else if(bal < -1){
			if(heightDiff(current->right) > 0){
				// std::cout << "right left" << std::endl;
				leftLeft(current->right, current);
				rightRight(current, parent);
			}else{
				// std::cout << "right" << current->value << std::endl;
				rightRight(current, parent);
			}
		}
	}
	path.clear();
}

void AVLTree::rightRight(Node* current, Node* parent){
	Node* temp = current;
	current = current->right;
	temp->right = current->left;
	if(temp == root){
		root = current;
	}
	current->left = temp;
	if(parent != NULL){
		if(parent->left == temp){
			parent->left = current;
		}else if(parent->right == temp){
			parent->right = current;
		}
	}
}

void AVLTree::leftLeft(Node* current, Node* parent){
	Node* temp = current;
	current = current->left;
	temp->left = current->right;
	if(temp == root){
		root = current;
	}
	current->right = temp;
	if(parent != NULL){
		if(parent->left == temp){
			parent->left = current;
		}else if(parent->right == temp){
			parent->right = current;
		}
	}
}

int AVLTree::height(Node* current){
	int level = 1;
	int total = 0;
	total = levelCount(current,total,level);
	// std::cout << total << "height" << std::endl;
	return total;
}

int AVLTree::levelCount(Node* current, int total, int level){
	if(current != NULL){
		// we have reached a lower level, increment the count
		level++;
		// keep track of the highest level number
		if (level > total) {
			total = level;
		}
		// go to the left, if there is something there, it will
		// see the level, if it is greater than the highest, we will record it.
		levelCount(current->left,total,level);
		// same on the right.
		levelCount(current->right,total,level);
		// we reached a new level, now we are going back
		level--;
	}
	return total;
}

int AVLTree::heightDiff(Node* current){
	int heightL = height(current->left);
	int heightR = height(current->right);
	int diff = heightL - heightR;
	return diff;
}

void AVLTree::postOrder(Node* current){
	if(current == NULL){
		return;
	}
	postOrder(current->left);
	postOrder(current->right);
	if(first != true){
		std::cout << " ";
	}else{
		first = false;
	}
	std::cout << current->value;
}

void AVLTree::preOrder(Node* current){
	if(current == NULL){
		return;
	}

	if(first != true){
		std::cout << " ";
	}else{
		first = false;
	}
	std::cout << current->value;

	preOrder(current->left);
	preOrder(current->right);
}

void AVLTree::inOrder(Node* current){
	if(current == NULL){
		return;
	}
	inOrder(current->left);

	if(first != true){
		std::cout << " ";
	}else{
		first = false;
	}
	std::cout << current->value;

	inOrder(current->right);
}

void AVLTree::traverse(std::string method){
	// std::cout << std::endl;
	if(method == "IN"){
		AVLTree::inOrder(root);
		std::cout << std::endl;
	}
	if(method == "PRE"){
		AVLTree::preOrder(root);
		std::cout << std::endl;
	}
	if(method == "POST"){
		AVLTree::postOrder(root);
		std::cout << std::endl;
	}
}

void AVLTree::insert(int number){
	Node* temp = new Node;
	temp->left = NULL;
	temp->right = NULL;
	temp->value = number;
	if(isEmpty()){		// if root is NULL update root
		root = temp;
		return;
	}
	Node* current = root;
	// std::cout << number << std::endl;
	while(current->value != number){	// while number is not found in the tree
		path.push_back(current);
		if(number > current->value){
			// std::cout << "GREATER" << std::endl;
			if(current->right == NULL){
				current->right = temp;		//add new node
				break;
			}else{
				current = current->right;		// move right side
			}
		}else if(number < current->value){
			// std::cout << "LESS" << std::endl;
			if(current->left == NULL){
				current->left = temp;		// add new node
				break;
			}else{
				current = current->left;		//move left side
			}
		}
	}
	balance();
}

void AVLTree::remove(int number){
	if(isEmpty()){		// if root is NULL do thing
		return;
	}
	bool found = false;
	Node* current;
	Node* parent = NULL;
	Node* newNode = NULL;
	current = root;
	while(current != NULL){
		if(current->value == number){
			found = true;
			break;
		}else{
			path.push_back(current);
			parent = current;
			if(number > current->value){
				//move right side
				current = current->right;
			}else{
				//move left side
				current = current->left;
			}
		}
	}
	if(found == true){
		// leaf node (no child)
		if(current->left == NULL && current->right == NULL){
			if(parent == NULL){
				delete current;
				root = NULL;
			}else if(current == parent->left){
				parent->left = NULL;
				delete current;
			}else{
				parent->right = NULL;
				delete current;
			}
		}
		if(current->right != NULL && current->left == NULL){  // single child
			if(parent == NULL){
				root = current->right;
				path.push_back(root);
				delete current;
			}else if(current == parent->left){
				parent->left = current->right;
				path.push_back(parent->left);
				delete current;
			}else{
				parent->right = current->right;
				path.push_back(parent->right);
				delete current;
			}
		}else if(current->right == NULL && current->left != NULL){
			if(parent == NULL){
				root = current->left;
				path.push_back(root);
				delete current;
			}else if(current == parent->left){
				parent->left = current->left;
				path.push_back(parent->left);
				delete current;
			}else{
				parent->right = current->left;
				path.push_back(parent->right);
				delete current;
			}
		}
		if(current->right != NULL && current->left != NULL){  // two child nodes
			// smallest value in right subtree
			Node* currRight = current->right;
			if(currRight->right == NULL && currRight->left == NULL){
				current->value = currRight->value;
				current->right = NULL;
				delete currRight;
			}else if((current->right)->left != NULL){		// right node has left children
				Node* swapParent = current->right;
				Node* swapNode = swapParent->left;

				while(swapNode->left != NULL){		// until smallest value
					swapParent = swapNode;
					path.push_back(swapParent);
					swapNode = swapNode->left;
				}
				current->value = swapNode->value;
				if(swapNode->right == NULL){
					delete swapNode;
					swapParent->left = NULL;
				}else{
					swapParent->right = swapNode->right;
					delete swapNode;
				}
			}else{		// right node had no left children
				current->value = currRight->value;
				current->right = currRight->right;
				delete currRight;
			}
		}
	}
	balance();
}

Node::~Node(){
}

AVLTree::~AVLTree(){
}

int main(){

	AVLTree tree;

	std::string instruct;
	std::vector<char> AorD;
	std::vector<std::string> value;
	std::string traversal;
	int count = 0;
	// while(std::getline(std::cin, instruct)){

	std::getline(std::cin, instruct);
	// instruct = "A20 A4 A8 PRE";
	int length = instruct.length();
	for(int i = 0; i < length; i++){
		if(instruct[i] == 'A' || instruct[i] == 'D'){
			AorD.push_back(instruct[i]);
			i++;
			value.push_back("0");
			while(isdigit(instruct[i])){
				count = value.size()-1;
				value[count] += instruct[i];
				i++;
			}
		}
		if(instruct[i] == 'I'){
			traversal = "IN";
		}else if(instruct[i] == 'P' && instruct[i+1] == 'O'){
			traversal = "POST";
		}else if(instruct[i] == 'P' && instruct[i+1] == 'R'){
			traversal = "PRE";
		}
	}
	for(int i = 0; i < AorD.size(); i++){
		if(AorD[i] == 'A'){
			tree.insert(std::stoi(value[i]));
		}else{
			tree.remove(std::stoi(value[i]));
		}
	}
	if(tree.isEmpty()){
		std::cout << "EMPTY" << std::endl;
	}else{
		tree.traverse(traversal);
	}
	instruct.clear();
	AorD.clear();
	value.clear();
	traversal = "";
	tree.first = true;
	tree.root = NULL;
	tree.path.clear();
	// }
	return 1;
	// std::cout << tree.root->left->value << std::endl;
	// std::cout << tree.root->value << std::endl;
	// std::cout << tree.root->right->value << std::endl;

}