### Solution Developed In:

## The Question

For this article we will be covering Leetcode's '110. Balanced Binary Tree' question.

Question:

Given a

binary tree, determine if it isheight-balanced.

For this problem, aheight-balancedbinary 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:

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

## Explaining The Question

This Question is rated **Easy**. Which is for the most part accurate. I do not believe that this question is easy to solve although. You need to know a handful of techniques and patterns to be able to solve this.

This question is very close to the **Maximum Depth of Binary Tree**. Although in this case, we're going to need to keep track of the height of every **subtree** on every **node**, so we can ask the question 'Does my left or right tree differ in height by 1?'.

What Leetcode has asked us to do is to determine if the tree is **height-balanced**. Which is a **Binary Tree** in which the left and right subtrees of every node differ in height by no more than 1.

## Recommended Knowledge

- Binary Tree
- Depth First Search
- Post Order Traversal
**Maximum Depth of Binary Tree**- Recursive Depth First Search

## What do we know?

- We have a
(Most times, it could be empty)*binary tree* - We need to find the height of the left and right subtrees of
**every node**.

## How we're going to do it:

We're going to use Post Order Traversal to find the height of the left and right subtrees of **every node**. We do this by passing a **height** parameter to the each subtree, counting the number of nodes it takes until it hits the bottom of the tree. Meaning that once it hits the bottom most node, we have found the height of the tree.

Now we know the height of the left and right subtrees. All we do now is ask, 'Does my left or right tree differ in height by 1?'. If any of them violate this, we set our flag to false.

- Set ourself a
`flag`

to true. So by default, we're going to assume that the tree is height-balanced. Until we find a node that violates this, we're going to set our flag to false. - Perform a post order traversal of the tree. Where we pass a
`height`

parameter to each node. - Which gives us the left and right heights of each node.
- We ask the question, 'Does my left or right tree differ in height by 1?'. If any of them violate this, we set our flag to false.

## Big O Notation:

Time Complexity:

*O(**n**)*| Whereis the number of nodes in our*n*| As we're going to traverse all of the nodes within the tree.*Binary Tree*Space Complexity:

*O(**n**)*| Whereis the number of nodes in our*n*| As in the worst case, we're going to have to store the entire height of the tree in the call stack.*Binary Tree*

## Leetcode Results:

See Submission Link:

- Runtime: 70 ms, faster than
of JavaScript online submissions for Balanced Binary Tree*95.74%* - Memory Usage: 47.1 MB, less than
of JavaScript online submissions for Balanced Binary Tree*63.74%*

# The Solution

```
/**
* 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 {boolean}
*/
var isBalanced = function (root) {
// A flag to check if the tree is balanced or not
let flag = true;
// Helper function to check if the tree is balanced or not
const get_heights = (node, height) => {
// Empty tree? It's 0 in height
if (!node) {
return 0;
}
// Get my left and right heights
// by adding 1 to the height of the left and right subtrees.
// each time we move down them
const left_height = get_heights(node.left, height + 1);
const right_height = get_heights(node.right, height + 1);
// Let's use some math.
// Technically, if we have a balanced tree, the difference
// should always be 0. But because, this question is awkward, we need to check if
// if its diff is greater than 1. So we minus the two by using absolutes values and asking
// if the diff in this sub tree was greater than 1. If so bad un balanced.
if (Math.abs(right_height - left_height) > 1) {
flag = false;
}
// Return the height of the tree
// By returning whoever had the bigger height and adding 1 (Our current node)
return Math.max(left_height, right_height) + 1;
};
// Call the helper function
get_heights(root, 0);
// Get the flag back to base. :D
return flag;
};
```

## Top comments (0)