import java.util.*;

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

  private class Node {
    Key key;
    Value val;
    Node left, right;
    int count; //num of nodes below
    
    public Node(Key k, Value v) {
      key = k;
      val = v;
    }
  }
  //num of keys less than k
  public int rank(Key k) {
    return rank(k, root);	
  }

  private int rank(Key k, Node x) {
    if(x == null) return 0;
    int cmp = k.compareTo(x.key);

    if(cmp < 0) return rank(k, x.left);
    else if(cmp > 0) return 1 + size(x.left) + rank(k, x.right);
    else return size(x.left);
  }

  public Key min() {
    Node x = min(root);
    if(x == null) return null;
    return x.key;
  }

  private Node min(Node x) {
    if(x == null) return null;
    if(x.left == null) return x;
    return min(x.left);
  }

  public Key max() {
    Node x = max(root);
    if(x == null) return null;
    return x.key;
  }

  private Node max(Node x) {
    if(x == null) return null;
    if(x.right == null) return x;
    return max(x.right);	
  }

  public Key floor(Key k) {
    Node x = floor(k, root);
    if(x == null) return null;
    return x.key;
  }

  //key 
  private Node floor(Key k, Node x) {
    if(x == null) return null;
    
    int cmp = k.compareTo(x.key);
    if(cmp < 0) return floor(k, x.left);
    else if(cmp > 0) {
      Node t = floor(k, x.right);
      if(t != null) return t;
      return x;
    }
    else return x;
  }

  public Key ceil(Key k) {
    Node x = ceil(k, root);
    if(x == null) return null;
    return x.key;	
  }

  private Node ceil(Key k, Node x) {
    if(x == null) return null;
    
    int cmp = k.compareTo(x.key);
    if(cmp < 0) {
      Node t = ceil(k, x.left);
      if(t != null) return t;
      return x;
    }
    else if(cmp > 0) return ceil(k, x.right);
    else return x;
  }

  public int size() {
    return size(root);
  }

  private int size(Node x) {
    if(x == null) return 0;
    return x.count;
  }

  private Node put(Node x, Key k, Value v) {
    if(x == null) return new Node(k, v);
    int cmp = k.compareTo(x.key);
    if(cmp > 0) 
      x.right = put(x.right, k, v);
    else if(cmp < 0) 
      x.left = put(x.left, k, v);
    else 
      x.val = v;
    
    x.count = 1 + size(x.left) + size(x.right);
    return x;
  }

  public void put(Key k, Value v) {
    root = put(root, k, v);	
  }

  public Value get(Key k) {
    Node x = root;
    
    while(x != null) {
      int cmp = k.compareTo(x.key);
      if(cmp > 0) x = x.right;
      else if(cmp < 0) x = x.left;
      else return x.val;		
    }
    
    return null;
  }

  public void delete(Key k) {
    root = delete(k, root);	
  }

  private Node delete(Key k, Node x) {
    if(x == null) return null;
    
    int cmp = k.compareTo(x.key);
    if(cmp < 0) x.left = delete(k, x.left);
    else if(cmp > 0) x.right = delete(k, x.right);
    else {
      if(x.right == null) return x.left;
      
      Node t = x;
      x = min(t.right);
      x.right = deleteMin(t.right);
      x.left = t.left;		
    }
    x.count = 1 + size(x.left) + size(x.right);
    return x;
  }

  private void inorder(Node x, Queue<Key> q) {
    if(x == null) return;
    inorder(x.left, q);
    q.add(x.key);
    inorder(x.right, q);
  }

    public Iterable<Key> iterator() {
    Queue<Key> q = new LinkedList<Key>();
    inorder(root, q);
    return q;
  }

  public void print() {
    for(Key k : iterator()) 
      System.out.print(k + " ");
    System.out.println();
  }

  public void deleteMin() {
    root = deleteMin(root);
  }

  private Node deleteMin(Node x) {
    if(x == null) return null;
    if(x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.count = 1 + size(x.left) + size(x.right);
    return x;		
  }

  public void deleteMax() {
    root = deleteMax(root);	
  }

  private Node deleteMax(Node x) {
    if(x == null) return null;
    if(x.right == null) return x.left;
    x.right = deleteMax(x.right);
    x.count = 1 + size(x.left) + size(x.right);
    return x;
  }


  public static void main(String[] args) {
    BST<Integer, String> bst = new BST<Integer, String>();
    bst.put(1, "a");
    bst.put(2, "b");
    bst.put(3, "c");
    bst.put(4, "d");
    bst.put(5, "e");
    bst.put(6, "f");
    
    System.out.println(bst.rank(6));
    bst.print();
    
    bst.delete(2);
    bst.print();
    bst.deleteMax();
    bst.deleteMin();
    bst.print();
    bst.delete(4);
    bst.print();
  }
}