What makes this question special is this tweet.

He questions the interview process, I am with him. But whatever it is, it is.

Question : Invert a binary tree. Return the root of the inverted tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9
    
    to
   
     4
   /   \
  7     2
 / \   / \
9   6 3   1

 I would request you to change tabs or minimize your browser and give a good 30-40 minutes before seeing the solution.

Solution :-
As you can see in the example, all nodes have their siblings inverted or swapped! So we can recursively swap siblings for every node. But we cannot do it in one function, hence using another function to do the recursion work is required.

void inv(TreeNode* root){
    if(root==NULL)
        return;

    swap(root->left, root->right);

    inv(root->left);
    inv(root->right);
}

TreeNode* Solution::invertTree(TreeNode* root) {
    inv(root);
    return root;
}

The Time Complexity : O(n), since each node is visited once. Here n is the number of nodes.
The Space Complexity : O(h), as this many function calls will be put on the stack in the worst case, here h is the height of the binary tree. h ∈ O(n)

The full working code is available at Github, you can star the repository to get updates. I am also maintaining an Interview-Question-Wiki, kindly star and contribute. You can also follow this blog for more such posts. Comment in your queries, report bugs, discuss!