Print a BST In Order

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

Reminder: tree traversals. A traversal visits every node of a tree exactly once. The three classic orders only differ in WHEN a node is visited compared with its two subtrees: - in-order: left subtree, then the node, then the right subtree - pre-order: the node, then the left subtree, then the right subtree - post-order: the left subtree, then the right subtree, then the node

In-order is the special one for a BST. Everything smaller than a node is on its left and everything larger is on its right, so an in-order traversal visits the values from smallest to largest. For the tree below it visits 1 3 6 8 10 14.

      8
     / \
    3   10
   / \    \
  1   6    14

Requirements: 1. When node is null, return straight away: an empty subtree adds nothing. 2. Otherwise traverse node.left, then call visit(node, sb), then traverse node.right. 3. Let visit add the value: it already puts 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.