Question

Create at least 25 random ISBN keys and insert all random ISBN keys into a Binary Tree. Write a function to determine if the Binary Tree is a BST or not a BST. In addition validate AVL balance condition.

Hint: Should you proceed to validate AVL if the binary tree did not produce BST?

Report the problems. You don’t need to fix anything. Also, do not hard code the tree inside the code.

This needs to be done in Java.

Answer 1

//JAVA CODE TO COPY//


import java.util.Random;

//tree node class
class TreeNode
{
    int            value;
    TreeNode Left;
    TreeNode Right;

    TreeNode(int k)
    {
        value = k;
    }
}

class BST_AVL
{
    //checking if tree is BST
    //if its not an bst then it cant be AVL tree
    public static boolean isBST(TreeNode node)
    {
        return (isBSTUtil(node, 0, 100));
    }

    public static boolean isBSTUtil(TreeNode node, int min, int max)
    {

        if (node == null)
            return true;

        if (node.value < min || node.value > max)
            return false;

        return (isBSTUtil(node.Left, min, node.value - 1) && isBSTUtil(
                node.Right, node.value + 1, max));
    }

    public static boolean isBalanced(TreeNode root)
    {
        int left_side;
        int right_side;

        if (root == null)
            return true;

        left_side = height(root.Left);
        right_side = height(root.Right);

        if (Math.abs(left_side - right_side) <= 1 && isBalanced(root.Left)
                && isBalanced(root.Right))
            return true;

        return false;
    }

    public static int max(int a, int b)
    {
        return (a >= b) ? a : b;
    }

    public static int height(TreeNode node)
    {
        if (node == null)
            return 0;

        return 1 + max(height(node.Left), height(node.Right));
    }

    //main driver method
    public static void main(String args[])
    {
        //array to hold random ISBN keys
        int isbn[]=new int[25];

        //Random class object
        Random rand = new Random();
        //to hold random isbn
        int num;
        //generating 25 random ISBN keys
        for(int i=0; i<isbn.length; i++)
        {
            num = rand.nextInt(1000000000);
            isbn[i] = num;
        }
        //inserting data(ISBN) for two different BST
        TreeNode t1 = new TreeNode(isbn[0]);
        t1.Left = new TreeNode(isbn[1]);
        t1.Right = new TreeNode(isbn[2]);
        t1.Right.Left = new TreeNode(isbn[3]);
        t1.Right.Right = new TreeNode(isbn[4]);

        TreeNode t2 = new TreeNode(isbn[5]);
        t2.Left = new TreeNode(isbn[6]);
        t2.Right = new TreeNode(isbn[7]);
        t2.Right.Left = new TreeNode(isbn[8]);
        t2.Right.Right = new TreeNode(isbn[9]);
        t2.Left.Left = new TreeNode(isbn[10]);
        t2.Left.Right = new TreeNode(isbn[11]);

        //checking if bst is avl or not
        if (isBST(t1) && isBalanced(t1))
            System.out.println("Tree t1 is AVL tree");
        else
            System.out.println("Tree t1 is not AVL tree");

        if (isBST(t2) && isBalanced(t2))
            System.out.println("Tree t1 is AVL tree");
        else
            System.out.println("Tree t1 is not AVL tree");
    }
}

//OUTPUT//

Comment down for any queries!
Please give a thumbs up if you are satisfied and helped with the answer :)