Check if a Binary Tree is Balanced in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital, I write about tech topics and teach…

Check if a Binary Tree is Balanced in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital, I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

This article looks at the interview question — Check if a binary tree is balanced.

In JavaScript programming, efficiently determining whether a binary tree is balanced is a common problem. A balanced binary tree is one in which the heights of the left and right subtrees of every node differ by at most one. Ensuring a binary tree is balanced is crucial for maintaining optimal performance and preventing issues such as skewed trees that can lead to inefficient operations. In this article, we will explore different approaches to check the balance of a binary tree in JavaScript, providing practical solutions to tackle this problem.

Understanding Binary Tree Balance

A binary tree consists of nodes, each having at most two child nodes — left and right. Checking whether a binary tree is balanced involves assessing the height difference of its left and right subtrees. A balanced tree exhibits equal or nearly equal heights on both sides, ensuring efficient traversal and search operations.

Approach 1: Recursive Height Calculation

One common method to check the balance of a binary tree is by recursively calculating the height of each subtree. This approach involves traversing the tree in a depth-first manner, visiting each node and comparing the heights of its left and right subtrees. By recursively computing the height difference at each node, we can determine whether the tree is balanced.

**Time Complexity **In the recursive height calculation, the time complexity is O(n²), where n represents the number of nodes in the binary tree. This is because for each node, the height of its left and right subtrees needs to be calculated recursively, resulting in redundant calculations as the same nodes are traversed multiple times.

**Recursive Height Calculation Implementation in JavaScript: Code **Let’s explore a JavaScript implementation of the recursive height calculation approach:

class TreeNode {
 this.left = null;
 this.right = null;
return 0;
}
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
if (root === null) {
return true;
}
const leftHeight = getHeight(root.left);
const rightHeight = getHeight(root.right);
const heightDiff = Math.abs(leftHeight - rightHeight);
if (heightDiff > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
 
tree.right = new TreeNode(3);
tree.left.left = new TreeNode(4);
tree.left.right = new TreeNode(5);
console.log("Is the tree balanced?", isBalanced(tree));In the provided example, we create a binary tree and check its balance using the `isBalanced` function. The `getHeight` function recursively computes the height of each subtree, while `isBalanced` compares the heights and returns a boolean value indicating whether the tree is balanced. ``` 

Approach 2: Bottom-Up Depth Calculation

Another approach to check the balance of a binary tree is by employing a bottom-up calculation of the depth. Starting from the leaves and moving upwards, we determine the depth of each subtree and compare their heights. This approach can be more efficient as it avoids redundant calculations by aggregating depth information from the leaves to the root.

**Time Complexity **The bottom-up depth calculation has a more efficient time complexity of O(n). This is because the calculation of the depth is performed in a bottom-up manner, starting from the leaves and aggregating the depth information towards the root. By avoiding redundant calculations and aggregating the depth data efficiently, this approach achieves linear time complexity.

**Bottom-Up Depth Calculation Implementation in JavaScript: Code **Here’s an implementation of the bottom-up depth calculation approach for checking the balance of a binary tree in JavaScript:

class TreeNode {
 this.left = null;
 this.right = null;
}
 
 
if (node === null) {
return 0;
}
const leftDepth = getDepth(node.left);
const rightDepth = getDepth(node.right);
return Math.max(leftDepth, rightDepth) + 1;
}
function isBalanced(root) {
if (root === null) {
return true;
}
function checkBalance(node) {
if (node === null) {
return true;
}
const leftDepth = getDepth(node.left);
const rightDepth = getDepth(node.right);
const heightDiff = Math.abs(leftDepth - rightDepth);
if (heightDiff > 1) {
return false;
}
return checkBalance(node.left) && checkBalance(node.right);
}
return checkBalance(root);
}
 
 
 
tree.right = new TreeNode(3);
tree.left.left = new TreeNode(4);
tree.left.right = new TreeNode(5);
#### Conclusion
 
Checking the balance of a binary tree is an essential task in JavaScript programming to ensure efficient data structures and optimal algorithm performance. By applying either the recursive height calculation or the bottom-up depth calculation approach, JavaScript developers can efficiently determine whether a binary tree is balanced. These approaches provide the foundation for designing robust algorithms and optimizing code that involves binary trees. Implementing balanced binary trees can significantly enhance the speed and efficiency of operations, resulting in better overall application performance.
 
#### JavaScript eBook
 
I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. [Check out the ebook now](https://www.mitrakos.com/ebook)!
 
I founded [Higglo Digital](https://higglo.io/) and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a *beautifully designed website*, [check us out](https://higglo.io/).
 
I also created [Wanderlust Extension](http://www.wanderlustapp.io/) to discover the most beautiful places across the world with highly curated content. Check it out!