Print a BST in Pre-Order

Complete the private helper preOrder(Node node, StringBuilder sb) so that preOrder() returns every value in the tree, in pre-order, separated by spaces.

Reminder: pre-order traversal. A traversal visits every node once. Pre-order visits the node FIRST, then its left subtree, then its right subtree (in-order, by contrast, is left, node, right). So the root always comes out first, and every parent comes out before its children.

      8
     / \
    3   10
   / \    \
  1   6    14

For this tree pre-order visits 8 3 1 6 10 14. That order records the shape of the tree: insert those values, in that order, into an empty BST and you rebuild exactly the same tree. That is why pre-order is the usual way to save or copy a tree.

Requirements: 1. When node is null, return straight away. 2. Otherwise call visit(node, sb) first, then traverse node.left, then traverse node.right. 3. visit already adds the value with a single space between values. 4. Use recursion, not a loop.

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.