public class UBST {
  public Node root;

  public UBST() {
    root = null;
  }

  public UBST(Node r) {
    root = r;
  }

  public void insert(int d) {
    Node temp = new Node(d);
    Node current = root;
    if (root == null)
      root = temp;
    else {
      while (current != null && current.right != null) {
        current = current.right;
        temp.parent = current;
      }
      temp = current;
      unbalance(temp);
    }
  }

  private void unbalance(Node t) {
    if (t.parent == root) {
      if (t.data < root.data) {
        Node temp = root;
        t = root;
        t.right = temp;
      }
    }
    else if (t.parent != root) {
      if (t.data < t.parent.data) {
        Node temp = t.parent;
        t = t.parent;
        t.right = temp;
        unbalance(t);
      }
    }
    else
      unbalance(t.right);
  }
}