Here is an implementation of how a preorder traversal
is done recursively.
public void preOrderTraversal(BinaryTree root){
if(root == null) return;
System.out.println(root);
preOrderTraversal(root.getLeft());
preOrderTraversal(root.getRight());
}
Notes:
- I am not sure of your approach; why are you returning a node? In any case, when the
root
is null with that approach you can return an "emptyNode
" and deal with it by an if statement. - As you can see I am only dealing with the
root
, with any level theroot
changes. Try to visualize this with a run-through and you will understand this concept. - You are missing a check for null nodes at the beginning (especially for
t
).
You can continue to adapt your results to this.
A final note is for the run-time complexity of this approach, I'd highly recommend understanding run-time complexities for recursive functions. It will help you a lot in the future. Check this wikipedia article for recurrence relations.