In Java

For this problem, assume that we have a binary search tree (BST) and every node of the tree stores an integer (a) Write a Java program that takes as input an integer, which we will call the key, and the textual representation of a binary scarch tree. The program then prints the integer stored in the first node of the tree, such that this node is the first visited node in a preorder traversal that also stores an integer smaller than the input integer. Input. The input consists of multiple lines. The first line contains one integer, the key. The second line contains one integer, n, the number of nodes in the tree. The next n lines represent the n nodes of the tree Each of these lines consists of four space-separated tokens. The first token is a string representing the label of the node. The second token is an integer representing the value of the node. The third and the fourth tokens are strings representing respectively the labels of the left and right children of the current node. The string "NONE" is used in place of the third and/or fourth tokens if a node does not have a left and/or a right child Sample input 6 A 10 B C B 5 DE C15 F G D 1 NONE NONE E 7 NONE NONE F 11 NONE NONE G 17 NONE NONE Output. The output consists of a single line. This line contains a single integer that corresponds to the value stored in the node that is first encountered during preorder traversal and that stores a value smaller than the given key. If a nodes of the tree store values larger than the given key, then the output is the statement "There is no node in the BST whose value is smaller than the given key." Sample output (for the above input)