Invert Binary Tree With JavaScript

In this article, I will be showing you how to solve the LeetCode Invert Binary Tree problem using a recursive approach. I'll explain each step of developing a solution to help you improve your problem solving skills.

Lets get right into it

The Problem

The question is asking us to invert a binary tree. Pretty simple right?

The structure of a binary tree node from LeetCode is as follows:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */

So the function takes in one parameter - root, and then returns the same root with the rest of the tree reversed.

The Solution

We will be using recursion to create a solution since I believe its the simplest approach. Within our base function LeetCode automatically generates:

var invertTree = function(root) {

};

We will create a function called reverseNode which will reverse a node's left and right nodes. This function will take in one parameter - node:

var invertTree = function(root) {
    const reverseNode = node => {

    }
};

The first part of function will be checking if the node is null. This would mean that there is either no root or there is no further part of the tree. If the node is null, we will return null from the function:

var invertTree = function(root) {
    const reverseNode = node => {
        if (node == null) {
            return null
        }
    }
};

This is essentially our way of ending the recursion so it doesn't run forever.

After that conditional statement, we will recursively call the reverseNode function passing in both node.left and node.right so it reverses both sides of the tree.

Adding that to our code looks like this:

var invertTree = function(root) {
    const reverseNode = node => {
        if (node == null) {
            return null
        }
        reverseNode(node.left);
        reverseNode(node.right);
    }
};

After that, we obviously have to actually reverse the node which means we will need to swap the left and right values. To do this, we will need a variable that stores node.left so we can hold the original value after changing it to node.right.

Lets call this variable holdLeft:

var invertTree = function(root) {
    const reverseNode = node => {
        if (node == null) {
            return null
        }
        reverseNode(node.left);
        reverseNode(node.right);
        let holdLeft = node.left;
    }
};

I'm using let to define the variable, but you could use const as well.

After declaringholdLeft, we can swap the left and right nodes by reassigning node.left to node.right and reassigning node.right to the holdLeft value:

var invertTree = function(root) {
    const reverseNode = node => {
        if (node == null) {
            return null
        }
        reverseNode(node.left);
        reverseNode(node.right);
        let holdLeft = node.left;
        node.left = node.right;
        node.right = holdLeft;
    }
};

We then want to return node from the function:

var invertTree = function(root) {
    const reverseNode = node => {
        if (node == null) {
            return null
        }
        reverseNode(node.left);
        reverseNode(node.right);
        let holdLeft = node.left;
        node.left = node.right;
        node.right = holdLeft;
        return node;
    }
};

Finally, to complete our solution, we will need to return reverseNode(root) from the invertTree function so that it reverses the tree passed into the function.

Our completed solution now looks like this:

var invertTree = function(root) {
    const reverseNode = node => {
        if (node == null) {
            return null
        }
        reverseNode(node.left);
        reverseNode(node.right);
        let holdLeft = node.left;
        node.left = node.right;
        node.right = holdLeft;
        return node;
    }

    return reverseNode(root);
};

Take Away

You've now learned how to invert a binary tree using the JavaScript programming language. Its a fairly simple, elegant solution that uses recursion to effectively invert the tree.

👌 Thanks for reading this article!

If you like what I do and would love to see more related content, follow me on my other social platforms:

GitHub: Blake-K-Yeboah

LinkedIn: Blake-K-Yeboah

You can also show your support by buying me a coffee 😃

Invert Binary Tree With JavaScript

Comments

More from this blog

Optimizing Website Performance for Speed and User Experience

Useful Web APIs For Your Next Project

How to use the Fetch API in JavaScript

Don't Make These Common Mistakes While Learning To Code

Understanding Units In CSS

The Problem

The Solution

Take Away

Command Palette

Comments

More from this blog

The Problem

The Solution

Take Away