Creating an AVL tree

      1. Create an AVL tree with a height of 3 where the root of the tree would be the imbalanced alpha node if another single node X is inserted into the tree. Show the creation of the tree starting with the empty tree. Show each individual step of inserting the nodes and at each step state which rotation was done (if a rotation was done). Each value in the tree must be an integer and unique. For this problem, you can use drawings and even the visualization tools. You don’t need to implement this problem. 2. For your AVL tree in the problem above, now what is the node X which causes the tree to be imbalanced with the alpha node at the root? Show inserting and balancing the tree. What type of imbalance is it? 3. Write an algorithm (in Java code) which has a tight bound runtime of O(n2 ). Your algorithm must: • Include at least one of the traversals we discussed in class on a BST • Store a String in each BST node • Do any simple String concatenation operation during the traversal. • Include your .java files to compile and run your code. Include instructions on how to run your O(n2 ) method with a static void main method and test input.