JAVA

Modify the public Node insert(Node node, int key) method of AVLTree.java so that we can see AVL tree when we print the pre-order traversal of the tree. DO NOT MODIFY THE NAME OF THE METHOD, RETURN TYPE AND LIST OF PARAMETERS PASSED IN METHOD. 1) Run the Class AVLTree.java and match the output given in the assignment. Below is the file in which students will have to modify insert method: AVLTree.java package avl; class AVLTree { Node root; int height(Node node) { if (node == null) return 0; return node.height; } // Get maximum of two integers int max(int a, int b) { return (a > b) ? a : b; } // Right rotate subtree rooted with y public Node rightRotate(Node y) { Node x = y.left; Node T2 = x.right; // Perform rotation x.right = y; y.left = T2; // Update heights y.height = max(height(y.left), height(y.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; // Return new root return x; } // Left rotate subtree rooted with x public Node leftRotate(Node x) { Node y = x.right; Node T2 = y.left; // Perform rotation y.left = x; x.right = T2; // Update heights x.height = max(height(x.left), height(x.right)) + 1; y.height = max(height(y.left), height(y.right)) + 1; // Return new root return y; } // Get Balance factor of node public int getBalance(Node node) { if (node == null) return 0; return height(node.left) - height(node.right); } public Node insert(Node node, int key) { // Normal BST insertion if (node == null) return (new Node(key)); if (key node.key) node.right = insert(node.right, key); else // Duplicate keys not allowed return node; return node; } // Preorder traversal of the tree. public void preOrder(Node node) { if (node != null) { System.out.print(node.key + " "); preOrder(node.left); preOrder(node.right); } } public static void main(String[] args) { AVLTree tree = new AVLTree(); /* Constructing tree */ tree.root = tree.insert(tree.root, 8); tree.root = tree.insert(tree.root, 14); tree.root = tree.insert(tree.root, 33); tree.root = tree.insert(tree.root, 21); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 55); System.out.println("Preorder traversal of constructed tree is : "); tree.preOrder(tree.root); } } Java helper files (DO NOT MODIFY): Node.java package avl; class Node { int key, height; Node left, right; Node(int d) { key = d; height = 1; } } Please note a few points: 1. Create 2 separate java files for the above code and place them in a package named avl. 2. Write your code in AVLTree.java in insert method.

EXPECTED OUTPUT: The constructed AVL Tree should be 14 40 8 21 55 Preorder traversal of constructed tree is 33 14 8 21 40 55