import java.util.*;

public class Main {
  public static void main(String[] args) {
    AVL myAVL = new AVL();
    myAVL.insert(10);
    myAVL.insert(9);
    myAVL.insert(8);
    myAVL.insert(7);
    myAVL.insert(6);
    myAVL.insert(5);
    myAVL.insert(4);
    myAVL.insert(3);
    myAVL.insert(2);
    myAVL.insert(1);
    myAVL.insert(15);
    
    // Trigger left-right rotation
    //myAVL.insert(14);


    Queue<TreeNode> q = new LinkedList<>();
    q.add(myAVL.root);

    int level = 1;
    while (q.size() != 0) {
      int currentLevelSize = q.size();
      // System.out.println("Current level is " + level);

      for (int i = 0; i < currentLevelSize; i++) {
        TreeNode currNode = q.poll();
        System.out.print(currNode.val + " ");

        if (currNode.left != null)
          q.add(currNode.left);
        if (currNode.right != null)
          q.add(currNode.right);

        // System.out.println(currNode.val);
      }

      System.out.println("");
      level++;
    }
  }
}

/* AVL Tree Node Definition */
class TreeNode {
  public int val; // Node value
  public int height; // Node height, default 0
  public TreeNode left; // left child node, default null node
  public TreeNode right; // right child node, default null node
  public TreeNode(int x) {
    val = x;
  }
}

class AVL {
  TreeNode root;

  /* Obtain Node's Height */
  int height(TreeNode node) {
    // Null node's height is -1, leaf node's height is 0
    return node == null ? -1 : node.height;
  }

  /* Update Node Height */
  void updateHeight(TreeNode node) {
    // Node's height is the height of its higher subtree + 1
    node.height = Math.max(height(node.left), height(node.right)) + 1;
  }

  /* Obtain Balance Factor */
  int balanceFactor(TreeNode node) {
    // Null node has a balance factor of 0
    if (node == null)
      return 0;
    // Node's balance factor = left subtree's height - right subtree's height
    return height(node.left) - height(node.right);
  }

  /* Right Rotation */
  TreeNode rightRotate(TreeNode node) {
    TreeNode child = node.left;
    TreeNode grandChild = child.right;
    // Right rotate the node to its right child node
    child.right = node;
    node.left = grandChild;
    // Update the height of the node and the child node(the parent node after
    // right rotation)
    updateHeight(node);
    updateHeight(child);
    // Return the child node
    return child;
  }

  /* Left Rotation */
  TreeNode leftRotate(TreeNode node) {
    TreeNode child = node.right;
    TreeNode grandChild = child.left;
    // Left rotate the node to its left child node
    child.left = node;
    node.right = grandChild;
    // Update the height of the node and the child node(the parent node after
    // left rotation)
    updateHeight(node);
    updateHeight(child);
    // Return the child node
    return child;
  }

  /* Perform Self-balancing */
  TreeNode rotate(TreeNode node) {
    // obtain the balance factor of current node
    int balanceFactor = balanceFactor(node);
    // Skewed to left
    if (balanceFactor > 1) {
      if (balanceFactor(node.left) >= 0) {
        // right rotation
        return rightRotate(node);
      } else {
        // left-right rotation
        node.left = leftRotate(node.left);
        return rightRotate(node);
      }
    }
    // Skewed to right
    if (balanceFactor < -1) {
      if (balanceFactor(node.right) <= 0) {
        // left rotation
        return leftRotate(node);
      } else {
        // right-left rotation
        node.right = rightRotate(node.right);
        return leftRotate(node);
      }
    }
    // already balanced, no changes needed
    return node;
  }

  /* Node Insertion */
  void insert(int val) {
    root = insertHelper(root, val);
  }

  /* Node Insertion using recursion（dfs helper） */
  TreeNode insertHelper(TreeNode node, int val) {
    if (node == null)
      return new TreeNode(val);
    /* Find the insertion point - a null node, and replace it with the new Node
     * to perform node insertion */
    if (val < node.val)
      node.left = insertHelper(node.left, val);
    else if (val > node.val)
      node.right = insertHelper(node.right, val);
    else
      return node; // Abort the node insertion if it is a duplicated node
    updateHeight(
        node); // Update the height of node all the way back to the root node
    /* AVL Tree rotation for self-balancing */
    node = rotate(node);
    // Return the root node of the subtree
    return node;
  }

  /* Node Deletion */
  void remove(int val) {
    root = removeHelper(root, val);
  }

  /* Node Deletion using recursion（dfs helper） */
  TreeNode removeHelper(TreeNode node, int val) {
    if (node == null)
      return null;

    /* 1. Find node that is the desired node */
    if (val < node.val)
      // Since the value of deleted node is smaller, go to left subtree to find
      // the deleted node
      node.left = removeHelper(node.left, val);
    else if (val > node.val)
      // Since the value of deleted node is bigger, go to right subtree to find
      // the deleted node
      node.right = removeHelper(node.right, val);
    else { // deleted node found!
           // The degree of deleted node is 0 or 1
      if (node.left == null || node.right == null) {
        TreeNode child = node.left != null ? node.left : node.right;
        // when degree is 0 ，delete current node and return null node
        if (child == null)
          return null;
        // when degree is 1, replace current node with its child node
        else
          node = child;
      } else { // The degree of deleted node is 2
        TreeNode temp = node.right;
        while (temp.left != null) {
          temp = temp.left;
        }
        // replace the current node with the smallest node from its right
        // subtree
        node.right = removeHelper(node.right, temp.val);
        node.val = temp.val;
      }
    }
    updateHeight(node); // update the node height recursively
    /* AVL Tree rotation for self-balancing */
    node = rotate(node);
    return node; // return the root node of the subtree
  }
}