110. Balanced Binary Tree 🚀

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 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:

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

1. Binary Tree
2. Depth First Search
3. Post Order Traversal
4. Maximum Depth of Binary Tree
5. Recursive Depth First Search

What do we know?

1. We have a binary tree (Most times, it could be empty)
2. 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.

1. 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.
2. Perform a post order traversal of the tree. Where we pass a height parameter to each node.
3. Which gives us the left and right heights of each node.
4. 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) | Where n is the number of nodes in our Binary Tree | As we're going to traverse all of the nodes within the tree.

• Space Complexity: O(n) | Where n is the number of nodes in our Binary Tree | As in the worst case, we're going to have to store the entire height of the tree in the call stack.

Leetcode Results:

See Submission Link:

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

---

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;
};