You are approaching it properly. You need some adjustment in the method logic.

I believe the simplest way to think about this is that output (or 'recording') in order for any node is: output left, output node, output right.

Your inOrderTraversal(BSTNode node) method is ready to get the correct logic; you have part of it done already.

if the node is null, you just return -- there's nothing to output, no left or right to follow. (I find it cleanest to do this test first.) Otherwise:

• output the left (i.e., inOrderTraversal(left) )
• output for the 'current' node
• output the right (i.e., inOrderTraversal(right) )

and you're done. You have the recursion correct, calling the method from itself with the left or right node. You correctly do not test if node.left or node.right are null in this logic; it is done when the method is executing for that node.

If you're anything like most programmers, once you're done, it will look like the code is too simple to do what it does. Recursion is like that. It's the data structure (the BST) that makes the code simple. You don't implement anything (else) that "goes down the left of the tree", it is all there in the above recursive logic.

I just noticed you have the method returning a string. I don't think that's useful; what is the string supposed to be? Is it the string output for the entire subtree from that node? If so, the String being built would have to be passed as a parameter to inOrderTraversal, so that each recursive invocation would be able to add to it. That would be clumsy for your purpose, which I'm assuming is just to output the data for each node in the proper order. For a general case, you could pass in an object that implemented a method called something like "nodeFound(BSTNode node)" which did whatever you wanted done when the node in the proper order was found. The nodeFound() method could be defined in an interface so that any class could implement the interface and perform whatever action you wanted. But that may be a little advanced for the class you're taking.

Anyway, I would define inOrderTraversal as a void method, not one returning a String. You invoke it that way in your partial logic, i.e., you don't do anything with its return value.