Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/balanced-binary-tree

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]
- -10^4 <= Node.val <= 10^4

Explanation

Brute force approach

The brute force approach to verify if the tree is balanced or not is to get the height of left and right sub-trees. If the difference is not more than 1, we return true else false.

A C++ snippet of the above approach looks as below:

int height(node* node) {
    if (node == NULL)
        return 0;

    return 1 + max(height(node->left), height(node->right));
}

bool isBalanced(node* root) {
    int leftHeight, rightHeight;

    if (root == NULL)
        return 1;

    leftHeight = height(root->left);
    rightHeight = height(root->right);

    if (abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right))
        return 1;

    return 0;
}

The time complexity of the above approach is O(N^2).

Optimized solution

If we observe the approach closely, we can calculate the difference in the left and right sub-trees in the height recursion function. If at any point of time the difference between left and right subtree is greater than 1 we return false.

Let's check the algorithm first.

// isBalanced function
1. - if root == nullptr
     - return true

2. - return height(root) != -1

// height function
3. - if root == nullptr
     - return 0

4. - set leftHeight = height(root->left)
5. - set rightHeight = height(root->right)

6. - if leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1
     - return -1

7. - return 1 + max(leftHeight, rightHeight)

In the isBalanced function, we first check if the tree is empty or not. If it's empty, we return true. If not, we pass the root to the height function.

Inside the height function, we check if the root is empty. We return 0 for the empty element.

At steps 4 and 5, we recursively call left and right sub trees. In step 6, we check if the leftHeight or rightHeight is -1 or the absolute difference between left and right height is greater than 1. If the difference is above 1, we are returning -1. The flow fallback to step 2 and verify if -1 != -1. That's false and indicates the tree is not balanced. Else we return at step 7, 1 + max(leftHeight, rightHeight)

C++ solution

class Solution {
public:
    int height(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }

        int leftHeight = height(root->left);
        int rightHeight = height(root->right);

        if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        return 1 + max(leftHeight, rightHeight);
    }

    bool isBalanced(TreeNode* root) {
        if(root == nullptr) {
            return true;
        }

        return height(root) != -1;
    }
};

Golang solution

func maximum(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func height(root *TreeNode) int {
    if root == nil {
        return 0;
    }

    leftHeight := height(root.Left)
    rightHeight := height(root.Right)

    if leftHeight == -1 || rightHeight == -1 || int(math.Abs(float64(leftHeight - rightHeight))) > 1 {
        return -1
    }

    return 1 + maximum(leftHeight, rightHeight)
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }

    return height(root) != -1
}

Javascript solution

var height = function(root) {
    if(root === null) {
        return 0;
    }

    let leftHeight = height(root.left);
    let rightHeight = height(root.right);

    if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }

    return 1 + Math.max(leftHeight, rightHeight);
};

var isBalanced = function(root) {
    if(root === null) {
        return true;
    }

    return height(root) != -1;
};

Let's dry-run our algorithm to see how the solution works.

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

      root
        |
       [3, 9, 20, null, null, 15, 7]

// In isBalanced function
Step 1: if root == nullptr
           false

Step 2: return height(root) != -1

// In height function

       root
        |
       [3, 9, 20, null, null, 15, 7]

Step 3: if root == nullptr
           false

Step 4: leftHeight = height(root->left)
        root->left points to 9

          root
           |
       [3, 9, 20, null, null, 15, 7]

Step 5: if root == nullptr
           false

Step 6: leftHeight = height(root->left)
        root->left points to null
        So we get back here with value as 0 and it calls the next step.

        rightHeight = height(root->right)
        root->right points to null
        So we get back here with a value of 0, and it calls the next step.

        leftHeight = 0
        rightHeight = 0
        abs(0 - 0) > 1
        false

        if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
          false

        return 1 + max(leftHeight, rightHeight)
               1 + max(0, 0)
               1

Step 7: We fallback to Step 4 and execute the next line
        rightHeight = height(root->right)
        root->right points to 20

             root
              |
       [3, 9, 20, null, null, 15, 7]

Step 9: if root == nullptr
           false

Step 10: leftHeight = height(root->left)
         root->left points to 15

                              root
                               |
        [3, 9, 20, null, null, 15, 7]

Step 11: if root == nullptr
           false

Step 12: leftHeight = height(root->left)
         root->left points to null
         So we get back here with value as 0 and it calls the next step.

         rightHeight = height(root->right)
         root->right points to null
         So we get back here with a value of 0, and it calls the next step.

         leftHeight = 0
         rightHeight = 0
         abs(0 - 0) > 1
         false

         if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
           false

         return 1 + max(leftHeight, rightHeight)
                1 + max(0, 0)
                1

Step 13: We fallback to step 10 and execute next line
         rightHeight = height(root->right)
         root->right points to 7

                                 root
                                   |
        [3, 9, 20, null, null, 15, 7]

Step 14: if root == nullptr
           false

Step 15: leftHeight = height(root->left)
         root->left points to null
         So we get back here with value as 0 and it calls the next step.

         rightHeight = height(root->right)
         root->right points to null
         So we get back here with a value of 0, and it calls the next step.

         leftHeight = 0
         rightHeight = 0
         abs(0 - 0) > 1
         false

         if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
           false

         return 1 + max(leftHeight, rightHeight)
                1 + max(0, 0)
                1

Step 16: We fallback to Step 7 and execute next lines
         leftHeight = 1
         rightHeight = 1
         abs(1 - 1) > 1
         false

         if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
           false

         return 1 + max(leftHeight, rightHeight)
                1 + max(1, 1)
                2

Step 17: We fallback to Step 2 and execute next lines
         leftHeight = 1
         rightHeight = 2
         abs(1 - 2) > 1
         false

         if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
           false

         return 1 + max(leftHeight, rightHeight)
                1 + max(1, 2)
                3

Step 18: We return back to isBalanced function and execute the last return part
         return height(root) != -1
           3 != -1
           true

So we return the answer as true.