First off, always remember that you're working on a BST, not an unsorted binary tree or non-binary general tree. That means at all times you can rely on the BST invariant: every value in left subtree < this < every value in right subtree. (equality included on one of the sides in some implementations).
Example where this is relevant: in BST searching, if the value you're trying to find is less than this, there's no point looking in the right subtree for it; it's not there.
Other than that, treat it like you would any recursion problem. That means, for a given problem:
1) Determine what cases are trivial and don't require recursion. Write code that correctly identifies these cases and returns the trivial result. Some possibilities include a height-0 tree, or no tree (null root).
2) For all other cases, determine which of the following would make more sense: (both are usually possible, but one can be cleaner)
- What non-recursive work you could do to then reduce the problem to a sub-problem and return that solution (recursion at end, potentially tail recursion)
- What recursive work you would need to do first in order to solve this problem. (recursion at start, not tail recursion)
Having private helper methods is not necessarily a bad thing; so long as they serve a distinct and useful function you shouldn't feel bad for writing them. There are certainly some recursion problems that are much cleaner and less redundant when split into 3-4 methods rather than cramming them into one.
Take some BST problems and see if you can identify the general structure of the solution before you sit down to code it. Hope this helps! Also you may want to have a java tag on your question if you're specifically asking about BST stuff for Java.
