Binary tree mirror() how does this work?

Question

I have had some real difficulty in understanding the core of this snippet though it looks very simple and straightforward. Given a simple Binary tree, this famous function produces a mirrored result of the same tree.

void mirror(struct node* node) {
  if (node==NULL) {
    return;
  }
  else {
    struct node* temp;

    // do the subtrees
    mirror(node->left); //this part confuses me
    mirror(node->right); //so does this 

    // swap the pointers in this node
    temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
}

This will be the code. I have two questions on my mind after reading this code.

1. mirror(node->left) and mirror(node->right) places two consecutive function calls on the call stack. My understanding is, first, the function is called on the left node and then right. This process recurs as long as node is empty. But when it is not empty what does it return? Does it just come back to the call statement without returning anything?

2. How are these functions invoked from the call stack? It would be really helpful if someone runs through the function calls and tells how and why do we need two consecutive function calls.

P.S: Why aren't iterations used in this scope?

EDIT: quoting a useful comment by EOF, is it possible to tail-recurse this function by moving the swapping before the two recursive calls?

Answer 1

1. mirror(node->left) and mirror(node->right) places two consecutive function calls on the call stack.

That's an odd way to put it, and it may reflect a misunderstanding. At no one time does the call stack ever contains a representation of both those function calls.

My understanding is, first, the function is called on the left node and then right. This process recurs as long as node is empty. But when it is not empty what does it return?

The function has type void. It never returns anything.

Does it just come back to the call statement without returning anything?

Yes, when the function finishes, control resumes with the next statement after the function call.

2. How are these functions invoked from the call stack?

Functions are not invoked "from" the call stack. Stack frames are created for functions and pushed as part of the process of calling the function. The details are unspecified; compilers are responsible for generating code to do the right thing.

It would be really helpful if someone runs through the function calls and tells how and why do we need two consecutive function calls.

To mirror the whole tree means to reverse the children of every node. When processing a given node, the function must therefore ensure that that node's children are both mirrored. It accomplishes that by performing a recursive call for each one, and afterward swaps them.

Answer 2

So what is happening here is that the mirror() function is performing the mirror operation in post order. That is, the left sub-tree is processed, then the right sub-tree is processed, then the parent node. So the first thing it does is check whether the current node is null.

if (node == null) {
    return;
}

This will happen only after a leaf node is reached. A leaf node has null left and right pointers, thus it will effectively execute mirror(null) when it executes the mirror(node->left). Likewise with the right node. Since the node is null (e.g. this is the left or right pointer of a leaf node), there is nothing to do.

The calls to mirror(node->left) and mirror(node->right) cause the left and right child sub-trees to be processed. After that is complete, the left and right pointers are swapped in the current node and the mirror process is complete.