Invert Binary Tree With JavaScript
Recursive Algorithm To Invert A Binary Tree
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 useconst
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 😃