Having trouble understanding tree traversal recursive functions

Question

I am having some trouble understanding the recursive functions involved in preorder, inorder, and postorder tree traversal. I have some knowledge of recursion (but admittedly its not my strong suit). All of the seem to call themselves twice first making a call with the left child of the root and then with the right child. But how exactly is this possible? Wouldn't the call to the preOrder function with the left child return the flow of control back to the top, and the next call would never be executed?

void preOrder (Node* root) 
{
    if (root == NULL) return;
    cout<<root->val<<", ";
    preOrder(root->left);
    preOrder(root->right);
}

Answer 1

Wouldn't the call to the preOrder function with the left child return the flow of control back to the top, and the next call would never be executed?

Of course not. The recursive call works just like any other function call: after the function completion the control returns to the place of call. 'The place' means not only the point in the code but also the point on the call stack, which means the same set of variables is available again. Just like after returning from any other function.

For example if you have a tree

        A
       / \
      X   Y

and you call preorder on the A node, then it first prints the A contents, then calls preorder on X and on return it is back in preorder(A), so it proceeds to call preorder on Y.