
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; } }