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