I need help writing a code for AVL trees. Below is the code outline and what needs to be done. IGNORE THE getBFSITERATOR METHOD.

import java.util.Iterator;

public class AVLTree implements StringTree{

private class AVLNode{

//Do not change these variable names

String key;

String value;

AVLNode left;

AVLNode right;

//Place any additional fields you need here

//TODO implement the node class here

}

//Use this variable as your root

AVLNode root;

//You may use any additional fields here as you see fit

public void makeEmpty() {

// TODO Remove all elements from the AVL tree.

}

public int size() {

// TODO Return the number of elements currently in the tree.

return 0;

}

public void insert(String key, String value) {

// TODO Insert the pair into the AVLTree

// Throw an IllegalArgumentException if the client attempts to insert

public boolean insert (T x){

try {

root = insert (x, root);

countInsertions++;

return true;

} catch(Exception e){

// TODO: catch a DuplicateValueException instead!

return false;

}

}rt a duplicate key

}

public String find(String key) {

// TODO Return the value affiliated with the String key.

// Throw an ObjectNotFoundException if the key is not in the AVLTree

return null;

}

public Iterator getBFSIterator() {

// TODO Only complete this section if you wish to attempt the 10 points EC

// This function should return a BFSIterator: Starter code provided below

return null;

}

/* Define your private Iterator class below.

private class BFSIterator implements Iterator{

public boolean hasNext() {

// TODO Return true if the iterator has another value to return

return false;

}

public String next() {

// TODO Return the next value in a BFS traversal of the tree

// It should start at the root and iterate through left children before right

return null;

}

}

*/

}

//AVL TESTER CLASS

public abstract class AVLTester {

public static boolean verifyAVL(StringTree toTest){

// TODO Return true if toTest is an AVL implementation of a String tree and false otherwise.

// All StringTree interface methods must behave correctly

// You may assume that size() and isEmpty() return the correct values

// Other than this, do not assume anything about the tree toTest, including its start size.

return false;

}

// You may use as many static helper functions as you think are necessary

}

//STRING TREE CLASS

import java.util.Iterator;

public interface StringTree {

public void makeEmpty();

public int size();

public void insert(String key, String value);

public String find(String key);

public Iterator getBFSIterator();

}