[Aloisius]

It can't be just mirroring, because there's the obvious zero-op solution because "left" and "right" don't actually mean anything except when you're visualizing it for humans:

  struct NormalNode {
    int value;
    struct NormalNode *left;
    struct NormalNode *right;
  };

  struct ReversedNode {
    int value;
    struct ReversedNode *right;
    struct ReversedNode *left;
  };

  struct ReversedNode *reverseTree(struct NormalNode *root) {
    return (struct ReversedNode *)root;
  }

There. Now left is right and right is left.

[sangnoir]

This is genius. My C is rusty, but isn't this more than visualising for humans, if I cast a NormalNode as ReversedNode, traversal should be reversed, right? (I.e.reversed->right is normal->left

[Aloisius]

Yes, everything would be reversed. That version isn't actually how you'd do it if you actually for some reason wanted to use it in real software, it just was for illustration purposes to show "left" and "right" are just names and you don't need to change anything in memory to flip them.

A similar effect could be done in an OO language by having a base class NormalNode with two accessors, getLeft() and getRight() work normally and then a derived ReverseNode where getLeft() called super.getRight() and getRight() called super.getLeft(). With a proper compiler, the whole thing would simply be optimized away.