"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
Top comments (0)