public class BST<Key extends Comparable<Key>, Value> {
    private Node root;             // raiz da BST

    private class Node {
        private final Key key;       
        private Value val;           
        private Node left, right;    

        public Node(Key key, Value val) {
	    this.key = key;
	    this.val = val;
	}
    }

    public BST() {}

    public boolean isEmpty() {
	return root == null;
    }

   

    /* Retorna o valor correspondente a uma dada chave */
    public Value get(Key key) {
	return get(root, key);
    }
    
    private Value get(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else              return x.val;
    }

    /* retorna TRUE se a chave key contém um valor na tabela de símbolos */
    public boolean contains(Key key) {
	return get(key) != null;
    }

  

    /* Imprime os elementos da tabela de símbolo por ordem de chaves */
    public void inOrder() {
	inOrder(root);
    }
    
    private void inOrder(Node x) { 
        if (x == null) return; 
        inOrder(x.left); 
	StdOut.println(x.key + " "); 
        inOrder(x.right); 
    }


/*
---------------------
---------------------
---------------------
---------------------
---------------------
Abaixo temos os métodos que você deve implementar
---------------------
---------------------
---------------------
---------------------
---------------------
*/

     /* Adiciona um par (key, value) na tabela de símbolos 
        e retorna a RAIZ da árvore*/
    public Node put(Key key, Value val) {
	root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
       
    }



    /* Imprime os elementos da tabela de símbolos por nível da árvore, começando pela raiz

DICA: usar filas pode ser útil. Por exemplo, os seguintes comandos criam filas de chaves e de nós.

Queue<Key> keys = new Queue<Key>();
Queue<Node> queue = new Queue<Node>();

Os comandos abaixo podem ser úteis: 
queue.enqueue(nó) - coloca "nó" na fila "queue"
keys.enqueue(x.key) - coloca a chave do nó x na fila "keys"

Da mesma forma você pode usar os comandos queue.dequeue e keys.dequeue() 
    */
    public void levelOrder() {
	this.levelOrder(this.root);
    }
    
    private void levelOrder(Node x) { 
         
    }

    /* Imprime os elementos da tabela de símbolos por nível da árvore, começando das folhas no último nível 
     */
    public void levelOrderFolhas() {
	this.levelOrder(this.root);
    }
    
    private void levelOrderFolhas(Node x) { 
         
    }

    /* Retorna o valor associado à menor chave da tabela de símbolos */
    public Value min() {
	return min(root);
    }
    
    private Value min(Node x) {

    }

    /* Retorna o valor associado à maior chave da tabela de símbolos */
    public Value max() {
	return max(root);
    }
    
    private Value max(Node x) {

    }

    /* Retorna a quantidade de pares key-value salvos na tabela de símbolos */
    /* Você pode criar outras variáveis de isntância se achar necessário */
    public int size(){

    }

    /* imprime todas as chaves menores que key */
    public void menores(Key key){
	menores(root, key);
    }
    
    private void menores(Node x, Key key){

    }

    /* imprime todas as chaves maiores que key */
    public void maiores(Key key){
	maiores(root, key);
    }
    
    private void maiores(Node x, Key key){

    }

    
    /* imprime todas as chaves maiores que "menor" e menores que "maior" */
    public void entre(Key menor, Key maior){
	 entre(root, menor, maior);
    }
    
    private void entre(Node x, Key menor, Key maior){

    }

    /* Remove o nó com menor chave na tabela de símbolos e retorna o valor associado a ele */
    public Value removeMin() {
	return removeMin(root);
    }

    private Value removeMin(Node x) {

    }




/*
---------------------
---------------------
---------------------
---------------------
---------------------
O método "remove" abaixo é opcional e vale 1 ponto extra no EP
---------------------
---------------------
---------------------
---------------------
---------------------
*/
    
/* Remove o nó com chave "key" e retorna o valor correspondente a essa chave 
******** OBS: O seu algoritmo --NÃO-- deve ser recursivo
*/
    public Value remove(Key key){
	return remove(root, key);
    }
    
    private Value remove(Node x, Key key){

    }


    






    

    
    public static void main(String[] args) { 
        BST<String, Integer> st = new BST<String, Integer>();
        for (int i = 0; !StdIn.isEmpty(); i++) {
            String key = StdIn.readString();
            st.put(key, i);
        }

      StdOut.println();
      st.inOrder();
      /*
      Implemente aqui os testes para os seus métodos
       */

        
    }
}