Your task is to write the body of the createBST and the checkAVL functions. You
ID: 3729513 • Letter: Y
Question
Your task is to write the body of the createBST and the checkAVL functions. You have complete freedom in designing the BST class, and you can add any helper methods you need in the AVL BST class. You may introduce more private classes, but they have to be declared in the same file. Below is what the BTS, creatBTS, and checkAVL should produce after inputting the given numbers. Do not use math function Input Array checkAVL(): output: 82, 85, 153, 195, 124, 66, 200, 193, 185, 243, 73, 153, 76 false 5, 3, 7, 1 true 5, 1, 98, 100, 3, 5, 55, 3, 56, 50 true 297, 619, 279, 458, 324, 122, 505, 549, 83, 186, 131, 71 false 78 true public class AVL_BST{ public static boolean checkAVL(BST b){ //TO DO: write your code; return false; } public static BST createBST(int[] a){ //TO DO: write your code; return null; } public static void main(String[] args){ int[] A = {5,2,8,6,1,9,52,3}; BST b = createBST(A); System.out.println(checkAVL(b)); } } class BST{ }
Explanation / Answer
public class AVL_BST{
public static boolean checkAVL(BST b){
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if (b == null)
return true;
/* Get the height of left and right sub trees */
lh = height(b);
rh = height(b.right);
if (Math.abs(lh - rh) <= 1
&& checkAVL(b.left)
&& checkAVL(b.right))
return true;
/* If we reach here then tree is not height-balanced */
return false;
}
/* The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
public static int height(BST node)
{
/* base case tree is empty */
if (node == null)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(height(node.left), height(node.right));
}
/* A function that constructs Balanced Binary Search Tree
from a sorted array */
public static BST createBST(int[] a){
return sortedArrayToBSTHelper(a, 0, a.length-1);
}
// helper function
public static BST sortedArrayToBSTHelper(int arr[], int start, int end) {
/* Base Case */
if (start > end) {
return null;
}
/* Get the middle element and make it root */
int mid = (start + end) / 2;
BST node = new BST(arr[mid]);
/* Recursively construct the left subtree and make it
left child of root */
node.left = sortedArrayToBSTHelper(arr, start, mid - 1);
/* Recursively construct the right subtree and make it
right child of root */
node.right = sortedArrayToBSTHelper(arr, mid + 1, end);
return node;
}
public static void main(String[] args){
int[] A = {5,2,8,6,1,9,52,3};
BST b = createBST(A);
System.out.println(checkAVL(b));
}
}
class BST{
int data;
BST left, right;
BST(int d) {
data = d;
left = right = null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.