LeetCode 226 - Invert Binary Tree

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

Tweet by Max Howell

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;
};

LeetCode 226 - Invert Binary Tree - Recursive JavaScript Solution

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;
};

LeetCode 226 - Invert Binary Tree - Iterative JavaScript Solution