#ifndef RED_BLACK_TREE_H
#define RED_BLACK_TREE_H

#pragma once

template <typename Comparable>

template <typename T>

 public:
    enum Color {RED, BLACK};
    
    // TODO(student): implement
};

    private:
        enum Color {RED, BLACK};
        struct Node {
            T data;
            Color colour;
            Node* left;
            Node* right;
            Node(const T& item)
            : data(item)
            , colour(BLACK)
            , left(nullptr)
            , right(nullptr) {}
            Node(const T& item, Color color, Node* left_child, Node* right_child)
            : data(item)
            , colour(color)
            , left(left_child)
            , right(right_child) {}
        };
        Node* m_root;
    public:
        RedBlackTree() : m_root(nullptr) {}
        RedBlackTree(const RedBlackTree& tree);
        ~RedBlackTree();
        RedBlackTree& operator=(const RedBlackTree& rhs);
        Color color(const Node* node) const {
            if (node == nullptr)
                return BLACK;
            else
                return node->colour;
        }
        const Node* get_root() const {
            return m_root;
        }
        bool contains(const T& item) const {
            if (m_root == nullptr) {
                return false;
            } else {
                Node* temp = m_root;
                while (temp != nullptr) {
                    if (temp->data == item)
                        return true;
                    else if (temp->data < item)
                        temp = temp->right;
                    else
                        temp = temp->left;
                }
                return false;
            }
        }

#endif  // RED_BLACK_TREE_H

        const T& find_max() const {
            if (m_root == nullptr)
                throw std::invalid_argument("tree is empty");
            
            Node* temp = m_root;
            while (temp->right != nullptr) temp = temp->right;
            return temp->data;
        }
        const T& find_min() const {
            if (m_root == nullptr)
                throw std::invalid_argument("tree is empty");
            
            Node* temp = m_root;
            while (temp->left != nullptr) temp = temp->left;
            return temp->data;
        }
        void insert(const T& item);
        void remove(const T& item);
};