#ifndef BST_H_
#define BST_H_
#include <stdexcept>
#include <iterator>
#include <deque>
#include <stack>
#include <string>
#include <initializer_list>

class BinarySearchTree {
public:
	enum class TreeTraversal {INORDER, PREORDER, POSTORDER};
private:
	struct TreeNode{
		int key;
		TreeNode *left;
		TreeNode *right;
		TreeNode(int _key): key{_key}, left{nullptr}, right{nullptr}{}
	};
	TreeNode* root = nullptr;
	int size = 0;
	TreeTraversal method = TreeTraversal::INORDER;
	std::deque<int> queue;
	std::deque<TreeNode*> parents;
public:
	BinarySearchTree() = default;
	virtual ~BinarySearchTree(){
		deleteNode(root);
	}
	int getSize(){ return size; }
	int numOfNodes(){
		if(isEmpty()) return 0;
		std::deque<TreeNode *> queue;
		queue.push_back(root);
		int count = 0;
		while(!queue.empty()){
			TreeNode* curr = queue.front();
			queue.pop_front();
			++count;
			if(curr->left!=nullptr) queue.push_back(curr->left);
			if(curr->right!=nullptr) queue.push_back(curr->right);
		}
		return count;
	}
	int getHeight(){
		if(isEmpty()) return 0;
		struct Node{
			TreeNode* node;
			int level = 0;
			Node(TreeNode* _node, int _level):
				node{_node}, level{_level}{}
		};
		std::deque<Node> queue;
		queue.emplace_back(root,0);
		int maxLevel = 0;
		while(!queue.empty()){
			Node curr = queue.front();
			queue.pop_front();
			maxLevel = std::max(maxLevel,curr.level);
			if(curr.node->left!=nullptr)
				queue.emplace_back(curr.node->left,curr.level+1);
			if(curr.node->right!=nullptr)
				queue.emplace_back(curr.node->right,curr.level+1);
		}
		return maxLevel;
	}
	bool isEmpty() { return root==nullptr; }
	void setTraversalMethod(TreeTraversal method){
		this->method = method;
	}
	void add(int key){
		TreeNode *newNode = new TreeNode(key);
		if(isEmpty()){
			root = newNode;
			++size;
			return;
		}
		TreeNode* parent = nullptr;
		bool isLeft = false;
		TreeNode* curr = root;
		while(curr!=nullptr){
			parent = curr;
			if(curr->key == key){
				delete newNode;
				return;
			}
			else if(curr->key>key){
				curr = curr->left;
				isLeft = true;
			}
			else{
				curr = curr->right;
				isLeft = false;
			}
		}
		if(isLeft) parent->left = newNode;
		else parent->right = newNode;
		++size;
	}

	void remove(int key)
	    {
	        TreeNode *removeNode = findNode(key, root); //삭제 할 노드 검색
	        if(removeNode==nullptr) std::invalid_argument("삭제 할 키 존재x");

	        TreeNode *parent = nullptr; //부모노드
	        TreeNode *son = nullptr; //자식노드

	        bool isLeft = false; //왼쪽방향으로가면 true 아닐시 false

	        while(removeNode!=nullptr)
	        {
	            if(removeNode->key == key)
	                {
	                    break;
	                }

	                parent = removeNode;

	                if(removeNode->key > key) {
	                    removeNode = removeNode->left;
	                    isLeft = true;
	                }

	                else
	                {
	                    removeNode = removeNode->right;
	                    isLeft = false;
	                }

	            son = removeNode;
	        }
	        if(isLeft) parent = nullptr;
	        else son = nullptr;
	        --size;
	    }

	bool find(int key){
		parents.clear();
		return findNode(key,root)!=nullptr;
	}

	using dequeIterator = std::deque<int>::iterator;
	dequeIterator begin(){
		queue.clear();
		switch(method){
		case TreeTraversal::INORDER: inOrder(root); break;
		case TreeTraversal::PREORDER: preOrder(root); break;
		case TreeTraversal::POSTORDER: postOrder(root); break;
		}
		return queue.begin();
	}
	dequeIterator end(){ return queue.end(); }
private:
	void deleteNode(TreeNode* node){
		std::deque<TreeNode*> bfsQueue;
		bfsQueue.push_back(node);
		while(!bfsQueue.empty()){
			TreeNode* curr = bfsQueue.front();
			bfsQueue.pop_front();
			if(curr->left) bfsQueue.push_back(curr->left);
			if(curr->right) bfsQueue.push_back(curr->right);
			delete curr;
		}
	}
	TreeNode* findNode(int key, TreeNode* node){
		if(node==nullptr) return nullptr;
		TreeNode* curr = node;
		while(curr!=nullptr){
			if(curr->key==key) return curr;
			parents.push_front(curr);
			if(curr->key>key) curr = curr->left;
			else curr = curr->right;
		}
		return nullptr;
	}

};

#endif /* BST_H_ */