In-order Traversal: Recursive Implementation

For BST implementation of OrderedSet ADT, we must iterate over the nodes using in-order traversal, so the outcome is "ordered" (sorted).

We will try to implement a recursive in-order traversal first before implementing the iterator since the recursive implementation is easier to understand and implement.

Assume the Node class was public, and we have the reference variable root pointing to the root of a BST. The following statement must print the values in the BST "in order":

printInOrder(root);

Exercise Complete the implementation of printInOrder.

public static void printInOrder(Node<T> node) {
  // TODO Implement me!
  System.out.print(node.data + " ");
}
Solution
public static void printInOrder(Node<T> node) {
  if (node == null) {
    return;
  }
  printInOrder(node.left);
  System.out.print(node.data + " ");
  printInOrder(node.right);
}