import static java.lang.System.*;

class Tree {

    private class Node {
        String key;
        Queue<Integer> value;
        Node left;
        Node right;
		int level;

		public Node(String tmpkey){
			key = tmpkey;
			value = new Queue();
			left = null;
			right = null;
		}

			public Node(){
			key = null;
			value = new Queue();
			left = null;
			right = null;
		}
	}

    private Node root;
	private Node current;

    private void debugHelper(Node tree, int depth) {


		if (tree != null) {
			String padding;



			tree.level=depth;

			depth++;
			debugHelper(tree.left,depth);

			depth--;
			depth++;
			int num = 10;
			System.out.println(""+tree.level+" "+tree.key);
			String spaces = String.format("%"+num+"s", "");
			System.out.println(spaces);
			debugHelper(tree.right, depth);

		}




		// Your code here might be recursive
        //throw new UnsupportedOperationException();
    }

    private void outputHelper(Node tree) {
        // Your code here might be recursive
        throw new UnsupportedOperationException();
    }

    public void insert(String key, Integer linenum) {
		if (current == null) {
			root = new Node(key);
			current = root;
			System.out.println("- ROOT - new node: " + key );
			//root.value.insert(linenum);
		} else {
			if ((current.key.compareToIgnoreCase(key)) > 0) {
				// root is bigger than key
				if (current.left != null) {
					current = current.left;
					insert(key, linenum);
				} else {
					current.left = new Node(key);
					//current.left.value.insert(linenum);
					System.out.println("- NEW NODE: " + key );
					System.out.println("	" + current.left.key + " is left of " +current.key);
					current = root;

				}
			}
			else if ((current.key.compareToIgnoreCase(key)) < 0) {
				// key is bigger than root
				if (current.right != null){
					current = current.right;
					insert (key,linenum);
				} else {
					current.right = new Node(key);
					//current.right.value.insert(linenum);
					System.out.println("- NEW NODE: " + key );
					System.out.println("	" + current.right.key +" is right of " +current.key);
					current = root;
				}
			}

			else {
				System.out.println("A repeating word: '"+ key + "'");
				//current.value.insert(linenum);
				current = root;
				//throw new UnsupportedOperationException();
			}
		}
	}


    public void debug() {
		System.out.println("\ncalling debug success.\n");
		debugHelper(root, 0);


    }

    public void output() {
        // Show sorted words with lines where each word appears
        outputHelper(root);
    }

}