Requirements: Our goal is to quickly find the information associated with movies, sometimes based on a movie name (e.g. Gangster Squad), in other times based on the prefix of a name (e.g. Gangster*). In terms of key-value notations, your search key is the short or simplified title of a movie, and the associated value or data is the entire object of type MovieInfo, which contains more information on the movie and is defined in the following class: class Movie Info { public String shortTitle; //simplified movie title, e.g. "Gangster Squad" public String fullTitle; //full title including year, e.g. "Gangster Squad (2012)" public int ID; //integer ID } The BST index is implemented as a stand-alone class BSTIndex, with an inner class Node. Each node within a BSTIndex tree contains 4 fields: key (of type String), data (of type MovieInfo), and left and right links to the children nodes. The BST index tree should never contain duplicate nodes; i.e. each node key needs to be unique across the tree. You will complete the implementation of the following methods and operations in class BSTIndex. All BST operations should be implemented using recursion. [20 points] public int calcHeight() This method should calculate and return the height of the current BSTIndex tree. We define the height of a tree (similar to our lecture slides) as the maximum depth in the tree plus 1. The height of a tree with only one node is 1, and the height of an empty tree is 0. Important: Notice that this is a public method that calls another private method calcNode- Height (Node t) and passes it a reference to the root. This is a common way of structuring BST methods such that external client code will not have direct access to the tree root. You will thus be implementing the code in the private calcNodeHeight (Node t) method. This applies to the rest of the methods in this assignment as well. [15 points] public void insert Movie (Movie Info data) This method should insert the given data element into the proper place in the BST structure. If the input file turned out to have duplicate keys (i.e. repeated short movie titles), then your insertion method should detect that and not add the new duplicated movie to the tree. [20 points] public Movie Info findMovie (String key) This method should return the data element (i.e. the MovieInfo object) of the node where the movie's shortTitle matches the given key. Return null if the movie is not found. [20 points] public ArrayList getMoviesPrefix (String prefixStr) This method should return (as an ArrayList) all movies (i.e., full title) in the tree whose shortTitle begins with the passed prefix string. If no movies match the given prefix, noth- ing will be printed. The order of ArrayList does not matter, but make sure it includes each match. [15 points] public ArrayList inorder Traversal () This method should traverse the tree in order and return the IDs of the movie based on the key order of the tree.) The Index Tester class is provided which will test your BSTIndex class. The IndexTester creates an empty BSTIndex object then reads the data from an input movie file, builds a MovieInfo object for each row, and inserts it into the BST index (using the insert method you implemented in BSTIndex class). At this point, the BST index will be built for all the movie entries in the file. Then, the program will ask the user to enter a string. The code for parsing the input string and deciding which operation to invoke is part of the starter code. Here's an example of how a program run might look like. Note that the data file name is passed as an argument to the program's main() method here using the command line: > java IndexTester data/movies100K.txt Inserted 10000 records. Inserted 20000 records. Inserted 30000 records. Inserted 40000 records. Inserted 50000 records. Inserted 60000 records. Inserted 70000 records. Inserted 80000 records. Inserted 90000 records. Inserted 100000 records. Index building complete. Inserted 100000 records. Elapsed time = 2. The input data is available in the data folder on Canvas. Note that the full data file (movies.txt) is relatively large. You can copy the smaller extract (movies 100K.txt) for debugging. They are all in the same format: one movie per line, with fields ID, shortTitle, and fullTitle, separated by a tab character '\t'. Read IndexTester code to remind yourself how to read this data. 3. Implement all missing code in BSTIndex.java. This is the only file you are required to submit on Gradescope for this assignment. 4. Test your program with Index Tester on the available datasets, starting from the smaller one.