While I was just beginning my preparation, I came across this:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
— Max Howell (@mxcl) June 10, 2015
It maybe sarcastic, but big companies still choose to interview using this method and there's no way around it if we want to get in!
The quote scared me a bit as I am not the one who wrote Homebrew! I was merely starting out.
So only way to get over that fear, I feel this question to be the first one I should write about.
Question:



Solution:
a. Recursive
A simple preorder traversal is the best way forward.
While visiting the root node, we swap the left & right child and then visit the left & right child respectively.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
// Recursion must have a base condition.
if(root == null) {
return root;
}
// A simple swap of let & right nodes of a root.
let tmp = root.right;
root.right = root.left;
root.left = tmp;
// Recurse on both sides in Preorder Traversal.
invertTree(root.left);
invertTree(root.right);
return root;
};
b. Iterative
Implement the preorder traversal in iterative manner.
While visiting the root node, we swap the left & right child and then visit the left & right child respectively.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if(root == null) {
return root;
}
let stack = [root], node, tmp;
// Use stack as this problem is a variant of Depth First Traversal
while(stack.length) {
node = stack.pop();
if(node == null) {
continue;
}
// Simple swap of left & right node
tmp = node.right;
node.right = node.left;
node.left = tmp;
stack.push(node.left);
stack.push(node.right);
}
return root;
};
Conclusion
It's one of the most easy problem, that doesn't seem easy till you do it yourself.
What did you think? let me know down below.
- LeetCode
- Data Structures
- Algorithms
- Tutorials
- Interviews
- #Trees
- #Depth First Search
- #JavaScript
Abhijit Kar
I bring 5 years worth of industry experience to the table and everything I learnt from countless hours of experimentation over a decade.
Checkout :
Leave a Comment