#if !defined(BST_H)
#define BST_H

#include <string>
#include <utility>
#include <stack>

template <class Key, class Value>
class BST {
  class Node;

public:
	class Iterator {
	public:
		Iterator(Node * root) {
			if (!root) {
				current_ = nullptr;
				return;
			}
			leftmost(root);
			current_ = stack.top();
			stack.pop();
		}

		bool operator==(const Iterator& other) {
			return current_ == other.current_;
		}

		bool operator!=(const Iterator& other) {
			return current_ != other.current_;
		}
		Iterator& operator++() {
			leftmost(current_->right());

			if (stack.empty()) {
				current_ = nullptr;
				return *this;
			}

			current_ = stack.top();
			stack.pop();
			return *this;
		}

		const std::pair<const Key&, Value&> operator*() {
			return std::pair<const Key&, Value&>(current_->key(), current_->value());

		}

	private:
		void leftmost(Node* p) {
			while (p) {
				stack.push(p);
				p = p->left();
			}
		}

		Node * current_; //Node to keep track
		std::stack<Node*> stack;

};

	BST(){
		root_ = nullptr;
	}

	Value& operator[](const Key& newKey) {
		if (root_ == nullptr) {
			root_ = new Node(newKey);
			return root_->value();
		}
		return root_->lookup(newKey);

	}

	Iterator begin() {
		return Iterator(root_);

	}

	Iterator end() {
		return Iterator(nullptr);
	}

private:
	class Node {

	public:
		Node(Key newKey) : key_(newKey), value_(), left_(nullptr), right_(nullptr) {}

		Value& value(){return value_;}
		const Key& key() {return key_;}

		Value& lookup(const Key& aKey) {
			if (aKey == key_) {
				return value(); //can replae value(), left(), etc with value_, left_
			}

			if (aKey < key_) {
				if (left_ == nullptr) {
					left_ = new Node(aKey);
					return left_->value();
				}
				return left_->lookup(aKey);

			} else if (aKey > key_) {
				if (right_ == nullptr) {
					right_ = new Node(aKey);
					return right_->value();
				}
				return right_->lookup(aKey);
			}
			return value();
		}

		Node* left() {
			return left_;
		}

		Node* right() {
			return right_;
		}

	private:
		const Key key_;
		Value value_;
		Node * left_;
		Node * right_;
	};

	Node * root_;
};
#endif