How does the recursion preorder traversal algorithm go back to parent?

Question

public static void preorder(Node root) {
    if(root == null) return;

    root.printValue();
    preorder(root.getLeft());
    preorder(root.getRight());
}

I have tried to go through this function numerous times but i still can't figure out how after traversing through all the left children the algorithm goes back to the nearest ancestor(parent). Could someone explain this to me.

Answer 1

There's an implicit return at the end of your void method:

public static void preorder(Node root) {
    if(root == null) return;

    root.printValue();
    preorder(root.getLeft());
    preorder(root.getRight());
    return;
}

You always return to the method that called you. So, if the parent's method call makes another call for the child, then when the child's method call returns, it returns to the parent's. Right?

Hope that makes sense. Like Kon said, you should just run through the algorithm on paper. Or, better yet, if you know how to use a debugger, you can just step through your code in the debugger and see how it works.

Answer 2

When traversal reaches leaf node, it's left and right children will be NULL. And preorder(root.getLeft()) will pass NULL and will return. Same way the right will also return NULL. Then the stack pops and goes back to parent.

I think it would be best if you can dry-run this using a stack then you'll be able to better understand it.