Balanced Binary Tree Leetcode Solution

A binary tree is Height-balanced if the difference of heights of left and right subtree of every node in the tree is at most 1. In this problem, we are going to check for a balanced binary tree.

Table of Contents

Example

Not balanced

     1

  /     \

2         3

Balanced

Approach

It is intuitive to think that, for every node in the binary tree, we can check whether or not the left and right subtrees follow the required condition. That’s the “Brute Force” method.

But, in order to check whether the tree is balanced, the approach can be improved on grounds of Time & Space complexities.

We follow an approach such that we solve the problem in a Bottom-Up manner. Check whether the subtrees of a node are itself, balanced binary trees(or not) and obtain the height of the binary tree at the same time, which can be generalized using recursion.

Algorithm(Brute Force)

Start from the root and keep traversing the binary tree until the root becomes NULL
Retrieve the height of left and right subtrees using height() function
- If the difference is more than ‘1’:
  - return false. As the tree does not satisfy the balance condition
- Check the balance condition for left and right subtrees recursively
Print the result

Algorithm(Optimal)

If the tree is empty, we can say it’s balanced. If not, we can follow other steps:
Create a helper function to return the “height” of a current subtree, using recursion.
Height Function will return:
- -1, when it’s an unbalanced tree
- the height otherwise.
In case a subtree has left or right subtree unbalanced, or their heights differ by more than ‘1’, return -1.
Otherwise, return the height of this subtree as : 1 + max(left_height, right_height)

Implementation

C++ Program of Balanced Binary Tree Leetcode Solution

Brute Force Method

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    return max(height(root->left) , height(root->right)) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
    return true;

    int l = height(root->left) , r = height(root->right);
    //calling height function at every node
    if(abs(l - r) > 1)
        return false;

    return balanced(root->left) && balanced(root->right);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);
    
    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}

Optimal Method

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    int l = height(root->left);
    int r = height(root->right);
    if(l == -1 || r == -1 || abs(l - r) > 1)
        return -1;
    return max(l , r) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
        return true;

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


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);

    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}

Not Balanced

Java Program of Balanced Binary Tree Leetcode Solution

Brute Force

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;
        return Math.max(height(root.left) , height(root.right)) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

        int l = height(root.left) , r = height(root.right);
        if(Math.abs(r - l) > 1)
            return false;
        return balanced(root.left) && balanced(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}

Optimal Method

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;

        int l = height(root.left);
        int r = height(root.right);

        if(l == -1 || r == -1 || Math.abs(l - r) > 1)
            return -1;

        return Math.max(l , r) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

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


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.left.left = new treeNode(4);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}

Not Balanced

Complexity Analysis of Balanced Binary Tree Leetcode Solution

Time Complexity

The Brute Force method has a time complexity of O(N * N), in the worst case(skewed tree). However, the optimal approach works in O(N) time as we do a single pass only.

Space Complexity

O(N) in both the cases, as recursion uses the auxiliary stack space.