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 0005 0004 0008 0002 0007 0011 0001 0013 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 S java HW3_ 1 input.txt For exercise 2: S javac HW3_ 2.java $ java HW3. 2 input.txt