Question

Write code in java

Implement a method to build an AVL tree out of a sorted (ascending order) array of unique integers, with the fastest possible big O running time. You may implement private helper methods as necessary. If your code builds a tree that is other than an AVL tree, you will not get any credit. If your code builds an AVL tree, but is not the fastest big O implementation, you will get at most 12 points. You may use any of the Math class methods (max, min, abs, etc.) as needed.

Hint: Given that the input array is sorted, think of how you might build the tree without doing any rotations.

public class AVLTreeNode {

    public int key;

    public AVLTreeNode left, right;

    public char balanceFactor; // ‘/’, ‘\’, or ‘-‘

    public AVLTreeNode(key, left, right) {

        this.key = key;

        this.left = left;

        this.right = right;

        height = 0;

        balanceFactor = ‘-‘;

    }

}

// builds an AVL tree out of a sorted array of integer keys,

// returns the root of the tree, null if array is empty

public static AVLTreeNode buildAVLTree(int[] arr) {

    // COMPLETE THIS METHOD

}

Answer 1

ANSWERI

have used O(n) approach.

 AVLTreeNode buildHelper(int[] arr, int start, int end) {   if (start > end) { return null; } /* Get the middle element and make it root */ int mid = (start + end) / 2; /* left subtree */ AVLTreeNode left = buildHelper(arr, start, mid - 1); /* right subtree */ AVLTreeNode right = buildHelper(arr, mid + 1, end); AVLTreeNode node = new AVLTreeNode(arr[mid],left,right); return node; } public static AVLTreeNode buildAVLTree(int[] arr) {     int n = arr.length;     if(n == 0)      {               return null;    }       else    {               return buildHelper(arr,0,n-1);  } }