Find the Largest Value With Recursion

Complete the private helper findMax(Node node) so that findMax() returns the largest value in the tree. This time you solve it with recursion: a method that calls itself on a smaller piece of the problem.

Reminder: every subtree of a BST is a BST too. In a BST every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. Pick any node and look only at it and everything below it: that piece follows the same rule, so it is a smaller BST of its own. That is why recursion fits trees so well. A method can answer for one node by asking the same method about one child, until it reaches a node that can answer on its own, called the base case.

        50
       /  \
     30    70
    /  \     \
  20    40    80

Larger values always go right, so the largest value is at the end of the right links (80 in the picture). A node with no right child has nothing larger below it, so it holds the answer.

Requirements: 1. Base case: when node has no right child, return the value stored in node. 2. Otherwise return whatever findMax gives back for node.right. 3. Use recursion, not a loop. findMax() already returns -1 for an empty tree, so node is never null inside the helper. 4. Do not change the tree.

The Node class is provided - do not rename it and do not add public to it, because a Java source file may contain only one public class.

Do NOT write a main method.