JavaScript Algorithms: Balanced Binary Tree (LeetCode)

Photo by Adarsh Kummur on Unsplash

Description

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

Solution

First of all, let’s understand what is a binary tree. The binary tree is a data structure where each node has at most two children. And each node we can consider as a binary tree.

And what is the height of a binary tree? So, it’s debatable. For example, we have a node without any children. This node can either be viewed as 0 or 1. We are going to say that each node without children has a height of 1.

Let’s look at the examples:

Example 1:

The node 9 has no children and a height of 1. The node 15 has no children and a height of 1 as well as node 7. Node 20 has the same height in the left and right nodes.

And the root node has a height of the left node of 1 and the right node of two, the difference between is 1. In this case, we’re going to return true because 1 is not greater than 1.

Example 2:

In this example, let’s look at the root node. The left node has a height of 4 and the right node has a height of 1. The difference between them is greater than 1. So, in this case, we’re going to return false.

Let’s come up with a solution:

Thanks for reading! Looking forward to your feedback. See you soon ✌️

Enjoyed this article? If so, get more similar content by subscribing to Decoded, our YouTube channel!