I mostly get the recursively programmed in order tree Traversal, but theres just a small gap in my understanding that I want to clarify. when the first recursive method call moves the node pointer all the way to the left, why does the fact that there is a null node cause the method to stop at the last node, move past the recursive call and print the last node. Part of me can just accept that that's just what happens, but what I really don't get is why once you print the last left node, why does it move back up to the right, its as if it treats the recently printed node like it treats the null node. In my mind it would keep moving left, as if repeatedly hitting a wall. I'm not sure how well I'm explaining what I don't get, I'll happily try to rephrase and use pictures if it's not clear. I assume the recursive in order tree Traversal is very standard, though I know of two implementations that do the same thing, but I'll add the method code I'm using in Java to be sure.
public void print(Node<E> e){
if (e != null) {
print(e.left);
System.out.println(e.element);
print(e.right)
}
}
why does the fact that there is a null node cause the method to stop at the last node, move past the recursive call and print the last node
As long as you haven't reached the left most node, you will keep calling print(e.left). Once you reached the left most node, e.left of that node would be null, and print(null) will end the recursion. Once it returns, System.out.println(e.element); will print the left most node.
why once you print the last left node, why does it move back up to the right
Then print(e.right) will be executed. If the left most node has a right child, print(e.right) will recursively print the sub-tree of that right child. Otherwise, it will execute print(null), ending the recursion on that path.
Once print() of the left most node returns, you go back to print() of the parent of that node, so you call System.out.println(e.element); for that parent node, and so on...