Insert a Value Into a BST

Complete the private helper insert(Node node, int value) so that insert(int value) adds a value to the tree in the right place. Use recursion, a method that calls itself.

Reminder: where a new value goes in a BST. A BST keeps every smaller value in a node's left subtree and every larger value in its right subtree, and it never stores the same value twice. A new value always becomes a brand new leaf (a node with no children). To find its spot you walk down exactly the way a search does, going left when the value is smaller and right when it is larger, until you reach an empty spot.

Inserting 50, 30, 70, 20, 40 and 80 in that order builds the tree below. Inserting 35 afterwards walks 50, then 30, then 40, and lands as the left child of 40:

        50
       /  \
     30    70
    /  \     \
  20    40    80
       /
     35

The helper returns the node that should sit in its spot. An empty spot (null) returns the new Node. Any other node attaches the result of the recursive call to the correct side and then returns itself, which is why the public method writes root = insert(root, value).

Requirements: 1. When node is null, return a new Node holding value. 2. When value is smaller than node.value, insert into the left subtree and store the result in node.left. 3. When value is larger, do the same on the right with node.right. 4. When value is already in the node, change nothing. 5. Return node at the end.

childrenOf(int value) is provided so the tests can show the shape of your 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.