Java Assignment Solution on Binary Tree

• 26th Oct, 2021
• 17:21 PM

//Java program -> check if a given array is a binary search tree or not 

/*---TEST CASES--------------------------------------------------------
 Case 1: 2 4 5 FALSE
 Case 2: 10 5 15 2 7 11 25 1 TRUE
 Case 3: 50500 TRUE
 Case 4: 90 50 150 20 75 95 175 5 25 66 80 92 111 166 200 TRUE
 Case 5: 90 50 150 20 75 95 175 5 25 66 91 93 111 166 200 FALSE
 Case 6: 8 4 12 2 6 10 14 1 3 5 99 9 11 13 15 FALSE
 */
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // parse the array representing the binary search binaryTreeObj 
        int[] binaryTree;
        String input = sc.nextLine();
        if (input.equals("")) {
            binaryTree = new int[0];
        } else {
            String[] binaryTreeStrings = input.split(" ");
            binaryTree = new int[binaryTreeStrings.length];
            for (int i = 0; i < binaryTreeStrings.length; i++) {
                binaryTree[i] = Integer.parseInt(binaryTreeStrings[i]);
            }
            // check if this is a binary search tree, print the result 
            System.out.println(isBinarySearchTree(binaryTree));

        }

    }

    public static boolean isBinarySearchTree(int[] binaryTree) {
        //TODO fill this in, along with any deeded helper fuctions
        Main binaryTreeObj = new Main();
        try {
            binaryTreeObj.root = new CurrentNode(binaryTree[0]);
            binaryTreeObj.root.left = new CurrentNode(binaryTree[1]);
            binaryTreeObj.root.right = new CurrentNode(binaryTree[2]);
            binaryTreeObj.root.left.left = new CurrentNode(binaryTree[3]);
            binaryTreeObj.root.left.right = new CurrentNode(binaryTree[4]);
            binaryTreeObj.root.right.left = new CurrentNode(binaryTree[5]);
            binaryTreeObj.root.right.right = new CurrentNode(binaryTree[6]);
            binaryTreeObj.root.left.left.left = new CurrentNode(binaryTree[7]);
            binaryTreeObj.root.left.left.right = new CurrentNode(binaryTree[8]);
            binaryTreeObj.root.left.right.left = new CurrentNode(binaryTree[9]);
            binaryTreeObj.root.left.right.right = new CurrentNode(binaryTree[10]);
            binaryTreeObj.root.right.left.left = new CurrentNode(binaryTree[11]);
            binaryTreeObj.root.right.left.right = new CurrentNode(binaryTree[12]);
            binaryTreeObj.root.right.right.left = new CurrentNode(binaryTree[13]);
            binaryTreeObj.root.right.right.right = new CurrentNode(binaryTree[14]);
            binaryTreeObj.root.left.left.left.left = new CurrentNode(binaryTree[15]);
            binaryTreeObj.root.left.left.left.right = new CurrentNode(binaryTree[16]);
        } catch (ArrayIndexOutOfBoundsException ex1) {
            //ex1.printStackTrace();           
        } catch (UnsupportedOperationException ex2) {
            throw new UnsupportedOperationException();
        }
        return checkIsBST(root, Integer.MIN_VALUE,
                Integer.MAX_VALUE);
    }

    static CurrentNode root; //Root of the Binary Tree 

    /* Returns true if the given tree is a BST and its 
     values are >= min and <= max. */
    static boolean checkIsBST(CurrentNode node, int min, int max) {
        if (node == null) {
            return true;
        }
        if (node.data < min || node.data > max) {
            return false;
        }
        return (checkIsBST(node.left, min, node.data - 1)
                && checkIsBST(node.right, node.data + 1, max));
    }
}

/* Class containing left and right child of current node and key value*/
class CurrentNode {

    int data;
    CurrentNode left, right;

// Constructor
    public CurrentNode(int item) {
        data = item;
        left = right = null;
    }
}