Description
1 Exercise 1. Given node values, write a Java program that constructs a binary search tree and determines if the binary search tree is balanced or not. Your java file name must be HW3 1.java I.e: Given the binary search tree in Figure 1, the result should be “false”, not ”False” or ”something false”, only false or ”true” if tree is balanced. 2. Given node values and a value x, construct a binary search tree and check the binary search tree has a path where sum of the values in the path is equal to the given value x. The path is calculated from root to leaf. Your java file name must be HW3 2.java I.e: Given the binary search tree in Figure 1 and the value 20, the result should be “true” due to 5-8-7 path. The output must be; true 5-8-7 If the value 24, the result should be ”false”, even though there is a path 5-8-11 because 11 is not leaf. The output must be; false Figure 1: Binary Search Tree 1 2 Input Format On each exercise, your code must accept the input file as the below format. The values in the first row are use to construct a binary search tree, plotted as a binary search tree in Figure 1, and a number in the second row is x value: 5 4 8 2 7 11 1 13 22 You can create a binary search trees to test and validate your program using online visualization tool from https://www.cs.usfca.edu/~galles/visualization/BST.html 3 How to Run Your Code For exercise 1; $ javac HW3 1.java $ java HW3 1 input.txt For exercise 2; $ javac HW3 2.java $ java HW3 2 input.txt 4 Notes 1. The homework must be original, individual work. Duplicate or very similar homeworks are both going to be considered as cheating. 2. You can ask questions about the homework via Microsoft Teams group. 3. Late submission will not be accepted! 4. You are going to submit your codes to Microsoft Teams. The submission submitted in wrong submission format will not be graded: The submission format is given below: −.zip −−HW3 1.java −−HW3 2.java 5 Policy All work on assignments must be done with your own unless stated otherwise. You are encouraged to discuss with your classmates about the given assignments, but these discussions should be carried out in an abstract way. That is, discussions related to a particular solution to a specific problem (either in actual code or in the pseudocode) will not be tolerated. In short, turning in someone elses work(from internet), in whole or in part, as your own will be considered as a violation of academic integrity. Please note that the former condition also holds for the material found on the web as everything on the web has been written by someone else. 2