Invert Binary Tree - Google interview question

"You developed an app which has over a million downloads, that's cute! But can you invert a binary tree "?

Question: Invert a Binary Tree.

What's meant by "Invert Binary Tree ?"

It means for each node, the left-subtree of the node becomes the right-subtree and right-subtree becomes left-subtree.

Let's simplify the question step by step:

Step 1 > How to traverse the tree?
Aim : Our main aim is to:
1> visite each node.
2> swap left subtree and right subtree.
3> go deep in the respective subtree and repeat.

So it makes sense to use DFS in this case.

Step 2> How do we swap?
1> we could simply swap the sub-trees using a temporary container.

Let's visualize this :

Let's write some code :

var invertTree = function(root) {
    return dfs(root);
};

function dfs(root){
    if(root == null) return null;
    let temp = root.left;
    root.left = root.right;
    root.right = temp;
    dfs(root.left);
    dfs(root.right);
    return root;
}

That's it !, now you know how to solve a question which is frequently asked at google!

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/invertBinaryTree.js