Data Modelling & AI Data Structure & Algorithm

How to determine if a binary tree is height-balanced?

20 June 2025

3

A height balanced binary tree is a binary tree in which the height of the left subtree and right subtree of any node does not differ by more than 1 and both the left and right subtree are also height balanced.

In this article, we will look into methods how to determine if given Binary trees are height-balanced

Examples: The tree on the left is a height balanced binary tree. Whereas the tree on the right is not a height balanced tree. Because the left subtree of the root has a height which is 2 more than the height of the right subtree.

Naive Approach: To check if a tree is height-balanced:

Get the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.

Below is the implementation of the above approach.

C++

/* CPP program to check if
a tree is height-balanced or not */
 
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data,
pointer to left child and
a pointer to right child */
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int d)
    {
        int data = d;
        left = right = NULL;
    }
};
 
// Function to calculate the height of a tree
int height(Node* node)
{
    // base case tree is empty
    if (node == NULL)
        return 0;
 
    // If tree is not empty then
    // height = 1 + max of left height
    // and right heights
    return 1 + max(height(node->left), height(node->right));
}
 
// Returns true if binary tree
// with root as root is height-balanced
bool isBalanced(Node* root)
{
    // for height of left subtree
    int lh;
 
    // for height of right subtree
    int rh;
 
    // If tree is empty then return true
    if (root == NULL)
        return 1;
 
    // Get the height of left and right sub trees
    lh = height(root->left);
    rh = height(root->right);
 
    if (abs(lh - rh) <= 1 && isBalanced(root->left)
        && isBalanced(root->right))
        return 1;
 
    // If we reach here then tree is not height-balanced
    return 0;
}
 
// Driver code
int main()
{
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(8);
 
    if (isBalanced(root))
        cout << "Tree is balanced";
    else
        cout << "Tree is not balanced";
    return 0;
}
 
// This code is contributed by rathbhupendra

C

/* C program to check if a tree is height-balanced or not */
#include <stdio.h>
#include <stdlib.h>
#define bool int
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* Returns the height of a binary tree */
int height(struct node* node);
 
/* Returns true if binary tree with root as root is
 * height-balanced */
bool isBalanced(struct node* root)
{
    /* for height of left subtree */
    int lh;
 
    /* for height of right subtree */
    int rh;
 
    /* If tree is empty then return true */
    if (root == NULL)
        return 1;
 
    /* Get the height of left and right sub trees */
    lh = height(root->left);
    rh = height(root->right);
 
    if (abs(lh - rh) <= 1 && isBalanced(root->left)
        && isBalanced(root->right))
        return 1;
 
    /* If we reach here then tree is not height-balanced */
    return 0;
}
 
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
 
/* returns maximum of two integers */
int max(int a, int b) { return (a >= b) ? a : b; }
 
/*  The function Compute the "height" of a tree. Height is
   the number of nodes along the longest path from the root
   node down to the farthest leaf node.*/
int height(struct node* node)
{
    /* base case tree is empty */
    if (node == NULL)
        return 0;
 
    /* If tree is not empty then height = 1 + max of left
      height and right heights */
    return 1 + max(height(node->left), height(node->right));
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
// Driver code
int main()
{
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->left->left = newNode(8);
 
    if (isBalanced(root))
        printf("Tree is balanced");
    else
        printf("Tree is not balanced");
 
    getchar();
    return 0;
}

Java

/* Java program to determine if binary tree is
   height balanced or not */
 
/* A binary tree node has data, pointer to left child,
   and a pointer to right child */
class Node {
    int data;
    Node left, right;
    Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
class BinaryTree {
    Node root;
 
    /* Returns true if binary tree with root as root is
     * height-balanced */
    boolean isBalanced(Node node)
    {
        int lh; /* for height of left subtree */
 
        int rh; /* for height of right subtree */
 
        /* If tree is empty then return true */
        if (node == null)
            return true;
 
        /* Get the height of left and right sub trees */
        lh = height(node.left);
        rh = height(node.right);
 
        if (Math.abs(lh - rh) <= 1 && isBalanced(node.left)
            && isBalanced(node.right))
            return true;
 
        /* If we reach here then tree is not height-balanced
         */
        return false;
    }
 
    /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
    /*  The function Compute the "height" of a tree. Height
       is the number of nodes along the longest path from
       the root node down to the farthest leaf node.*/
    int height(Node node)
    {
        /* base case tree is empty */
        if (node == null)
            return 0;
 
        /* If tree is not empty then height = 1 + max of
         left height and right heights */
        return 1
            + Math.max(height(node.left),
                       height(node.right));
    }
 
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.left.left.left = new Node(8);
 
        if (tree.isBalanced(tree.root))
            System.out.println("Tree is balanced");
        else
            System.out.println("Tree is not balanced");
    }
}
 
// This code has been contributed by Mayank
// Jaiswal(mayank_24)

Python3

"""
Python3 program to check if a tree is height-balanced
"""
# A binary tree Node
 
 
class Node:
    # Constructor to create a new Node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# function to find height of binary tree
 
 
def height(root):
 
    # base condition when binary tree is empty
    if root is None:
        return 0
    return max(height(root.left), height(root.right)) + 1
 
# function to check if tree is height-balanced or not
 
 
def isBalanced(root):
 
    # Base condition
    if root is None:
        return True
 
    # for left and right subtree height
    lh = height(root.left)
    rh = height(root.right)
 
    # allowed values for (lh - rh) are 1, -1, 0
    if (abs(lh - rh) <= 1) and isBalanced(
            root.left) is True and isBalanced(root.right) is True:
        return True
 
    # if we reach here means tree is not
    # height-balanced tree
    return False
 
 
# Driver function to test the above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(8)
if isBalanced(root):
    print("Tree is balanced")
else:
    print("Tree is not balanced")
 
# This code is contributed by Shweta Singh

C#

using System;
 
/* C# program to determine if binary tree is
height balanced or not */
 
/* A binary tree node has data, pointer to left child,
and a pointer to right child */
public class Node {
    public int data;
    public Node left, right;
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
public class BinaryTree {
    public Node root;
 
    /* Returns true if binary tree with root as
    root is height-balanced */
    public virtual bool isBalanced(Node node)
    {
        int lh; // for height of left subtree
 
        int rh; // for height of right subtree
 
        /* If tree is empty then return true */
        if (node == null) {
            return true;
        }
 
        /* Get the height of left and right sub trees */
        lh = height(node.left);
        rh = height(node.right);
 
        if (Math.Abs(lh - rh) <= 1 && isBalanced(node.left)
            && isBalanced(node.right)) {
            return true;
        }
 
        /* If we reach here then tree is not height-balanced
         */
        return false;
    }
 
    /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
    /* The function Compute the "height" of a tree. Height
       is the number of nodes along the longest path from
       the root node down to the farthest leaf node.*/
    public virtual int height(Node node)
    {
        /* base case tree is empty */
        if (node == null) {
            return 0;
        }
 
        /* If tree is not empty then height = 1 + max of
        left height and right heights */
        return 1
            + Math.Max(height(node.left),
                       height(node.right));
    }
 
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.left.left.left = new Node(8);
 
        if (tree.isBalanced(tree.root)) {
            Console.WriteLine("Tree is balanced");
        }
        else {
            Console.WriteLine("Tree is not balanced");
        }
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// JavaScript program to check if a tree is height-balanced
//  A binary tree Node
 
class Node{
    // Constructor to create a new Node
    constructor(data){
        this.data = data
        this.left = null
        this.right = null
    }
}
 
// function to find height of binary tree
function height(root){
     
    // base condition when binary tree is empty
    if(root == null)
        return 0
    return Math.max(height(root.left), height(root.right)) + 1
}
 
// function to check if tree is height-balanced or not
function isBalanced(root){
     
    // Base condition
    if(root == null)
        return true
 
    // for left and right subtree height
    let lh = height(root.left)
    let rh = height(root.right)
 
    // allowed values for (lh - rh) are 1, -1, 0
    if (Math.abs(lh - rh) <= 1 && isBalanced(
    root.left)== true && isBalanced( root.right) == true)
        return true
 
    // if we reach here means tree is not 
    // height-balanced tree
    return false
}
 
// Driver function to test the above function
let root = new Node(1)
root.left = new Node(2)
root.right = new Node(3)
root.left.left = new Node(4)
root.left.right = new Node(5)
root.left.left.left = new Node(8)
if(isBalanced(root))
    document.write("Tree is balanced","</br>")
else
    document.write("Tree is not balanced","</br>")
 
// This code is contributed by ShinjanPatra
 
</script>

Output

Tree is not balanced

Time Complexity: O(n^2) in case of full binary tree.
Auxiliary Space: O(n) space for call stack since using recursion

Efficient implementation: Above implementation can be optimized by

Calculating the height in the same recursion rather than calling a height() function separately.

For each node make two recursion calls – one for left subtree and the other for the right subtree.
Based on the heights returned from the recursion calls, decide if the subtree whose root is the current node is height-balanced or not.
If it is balanced then return the height of that subtree. Otherwise, return -1 to denote that the subtree is not height-balanced.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a tree node
struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    Node(int k)
    {
        key = k;
        left = right = NULL;
    }
};
 
// Function to check if tree is height balanced
int isBalanced(Node* root)
{
    if (root == NULL)
        return 0;
    int lh = isBalanced(root->left);
    if (lh == -1)
        return -1;
    int rh = isBalanced(root->right);
    if (rh == -1)
        return -1;
 
    if (abs(lh - rh) > 1)
        return -1;
    else
        return max(lh, rh) + 1;
}
 
// Driver code
int main()
{
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(30);
    root->right->left = new Node(15);
    root->right->right = new Node(20);
 
    if (isBalanced(root) > 0)
        cout << "Balanced";
    else
        cout << "Not Balanced";
    return 0;
}

C

// C program to check if a tree is height-balanced or not */
#include <stdio.h>
#include <stdlib.h>
#define bool int
 
// Structure of a tree node
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
// Function to create a new tree Node
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
// Functio to check if tree is height balanced
int isBalanced(struct node* root)
{
    if (root == NULL)
        return 0;
    int lh = isBalanced(root->left);
    if (lh == -1)
        return -1;
    int rh = isBalanced(root->right);
    if (rh == -1)
        return -1;
 
    if (abs(lh - rh) > 1)
        return -1;
    else
        return lh > rh ? lh + 1 : rh + 1;
}
 
// Driver code
int main()
{
    int height = 0;
 
    struct node* root = newNode(10);
    root->left = newNode(5);
    root->right = newNode(30);
    root->right->left = newNode(15);
    root->right->right = newNode(20);
 
    if (isBalanced(root) > 0)
        printf("Balanced");
    else
        printf("Not Balanced");
 
    getchar();
    return 0;
}

Java

// Java code to implement the approach
 
import java.io.*;
import java.lang.*;
import java.util.*;
 
// Class to define the tree node
class Node {
    int key;
    Node left;
    Node right;
    Node(int k)
    {
        key = k;
        left = right = null;
    }
}
 
class GFG {
 
    // Driver code
    public static void main(String args[])
    {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(30);
        root.right.left = new Node(15);
        root.right.right = new Node(20);
 
        if (isBalanced(root) > 0)
            System.out.print("Balanced");
        else
            System.out.print("Not Balanced");
    }
 
    // Function to check if tree is height balanced
    public static int isBalanced(Node root)
    {
        if (root == null)
            return 0;
        int lh = isBalanced(root.left);
        if (lh == -1)
            return -1;
        int rh = isBalanced(root.right);
        if (rh == -1)
            return -1;
 
        if (Math.abs(lh - rh) > 1)
            return -1;
        else
            return Math.max(lh, rh) + 1;
    }
}

Python3

"""
Python3 program to check if a tree is height-balanced
"""
# A binary tree Node
 
 
class Node:
 
    # Constructor to create a new Node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function to check if tree is height-balanced or not
 
 
def isBalanced(root):
 
    # Base condition
    if root is None:
        return True
 
    # Compute height of left subtree
    lh = isBalanced(root.left)
 
    # If left subtree is not balanced,
    # return 0
    if lh == 0:
        return 0
 
    # Do same thing for the right subtree
    rh = isBalanced(root.right)
    if rh == 0:
        return 0
 
    # Allowed values for (lh - rh) are 1, -1, 0
    if (abs(lh - rh) > 1):
        return 0
 
    # If we reach here means tree is
    # height-balanced tree, return height
    # in this case
    else:
        return max(lh, rh) + 1
 
 
# Driver code
if __name__ == '__main__':
    root = Node(10)
    root.left = Node(5)
    root.right = Node(30)
    root.right.left = Node(15)
    root.right.right = Node(20)
    if (isBalanced(root) == 0):
        print("Not Balanced")
    else:
        print("Balanced")
 
# This code is contributed by Shweta Singh

C#

// C# code to implement the approach
 
using System;
 
// Class to define a binary tree node
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
public class BinaryTree {
    public Node root;
 
    // Function to check if tree is height balanced
    public virtual int isBalanced(Node root)
    {
        if (root == null)
            return 0;
        int lh = isBalanced(root.left);
        if (lh == -1)
            return -1;
        int rh = isBalanced(root.right);
        if (rh == -1)
            return -1;
 
        if (lh > rh + 1 || rh > lh + 1)
            return -1;
        else
            return Math.Max(lh, rh) + 1;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(5);
        tree.root.right = new Node(30);
        tree.root.right.left = new Node(15);
        tree.root.right.right = new Node(20);
 
        if (tree.isBalanced(tree.root) > 0) {
            Console.WriteLine("Balanced");
        }
        else {
            Console.WriteLine("Not Balanced");
        }
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// JavaScript program to check if Binary tree is height-balanced
 
// Class to define a binary tree node
class Node{
  
    // Constructor to create node of
    // binary tree
    constructor(data){
        this.data = data
        this.left = this.right = null
    }
}
 
// Function to check if the tree is height balanced
function isBalanced(root)
{
    if (root == null)
            return 0;
        int lh = isBalanced(root.left);
        if (lh == -1)
            return -1;
        int rh = isBalanced(root.right);
        if (rh == -1)
            return -1;
 
        if (Math.abs(lh - rh) > 1)
            return -1;
        else
            return Math.max(lh, rh) + 1;
}
 
// Driver code
let root = new Node(10)
root.left = new Node(5)
root.right = new Node(30)
root.right.left = new Node(15)
root.right.right = new Node(20)
 
if(isBalanced(root) > 0)
    document.write('Balanced',"</br>")
else
    document.write('Not Balanced',"</br>")
 
// This code is contributed by shinjanpatra
</script>

Output

Balanced

Time Complexity: O(n)

Because we are only one dfs call and utilizing the height returned from that to determine the height balance, it is performing the task in linear time.

Auxiliary Space: O(n)

Using Pair:

The idea is simple instead of calling two recursive function ‘isBalanced’ and ‘height’ we can use a pair in which first value will represent that if any subtree is balanced or not and second value will represent the height of the every subtree in this way we can easily find that if tree is balanced or not.

Follow the steps below to implement the above idea:

Define a helper function isBalancedfast that takes a root node as input and returns a pair of boolean and integer values representing whether the tree rooted at the given node is balanced and its height, respectively.
Define the base case for the recursion: if the root node is NULL, return a pair with first set to true and second set to 0.
Recursively call isBalancedfast on the left and right subtrees of the current node.
Retrieve the boolean and integer values from the returned pairs and set them to leftAns, rightAns, leftHeight, and rightHeight.
Calculate the height of the current node by taking the maximum height of its left and right subtrees and adding 1.
Check if the absolute difference between the heights of the left and right subtrees is less than or equal to 1. If so, set diff to true; otherwise, set it to false.
Set ans.first to true if leftAns, rightAns, and diff are all true; otherwise, set it to false.
Set ans.second to the height of the current node.
Return ans.
Define a public function isBalanced that takes a root node as input and calls the isBalancedfast helper function on the root node.
Return the first element of the pair returned by the isBalancedfast function. This represents whether the entire binary tree is balanced or not.

Below is the implementation of the above approach:

C++

//C++ code to implement the above approach
#include <bits/stdc++.h>
// using the standard namespace
using namespace std;
 
// defining the structure for tree nodes
struct Node {
    int val;
    Node *left, *right;
    Node(int v)
        : val(v)
        , left(nullptr)
        , right(nullptr)
    {
    }
};
 
// defining the Solution class to check if a binary tree is
// balanced
class Solution {
    // helper function to determine if a binary tree is
    // balanced
    pair<bool, int> isBalancedfast(Node* root)
    {
        // base case: if root is null, the tree is balanced
        // and has height 0
        if (root == NULL) {
            pair<bool, int> p = make_pair(true, 0);
            return p;
        }
        // recursively call isBalancedfast function on left
        // and right subtrees
        pair<int, int> left = isBalancedfast(root->left);
        pair<int, int> right = isBalancedfast(root->right);
 
        // retrieve whether left and right subtrees are
        // balanced
        bool leftAns = left.first;
        bool rightAns = right.first;
 
        // check the difference in heights of left and right
        // subtrees
        bool diff = abs(left.second - right.second) <= 1;
 
        // create a pair to store the answer (whether the
        // tree is balanced) and its height
        pair<bool, int> ans;
        // set the height of the current node
        ans.second = max(left.second, right.second) + 1;
        // if both subtrees are balanced and their heights
        // differ by at most 1, the tree is balanced
        if (leftAns && rightAns && diff) {
            ans.first = true;
        }
        // otherwise, the tree is not balanced
        else {
            ans.first = false;
        }
        return ans;
    }
 
public:
    // Function to check whether a binary tree is balanced
    // or not.
    bool isBalanced(Node* root)
    {
        return isBalancedfast(root).first;
    }
};
//Driver Code
int main()
{
    // create a binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(8);
 
    // create an object of the Solution class
    Solution obj;
    // check if the binary tree is balanced using the
    // isBalanced function
    if (obj.isBalanced(root)) {
        cout << "The given binary tree is balanced."
             << endl;
    }
    else {
        cout << "The given binary tree is not balanced."
             << endl;
    }
 
    return 0;
}
//This code is contributed by Veerendra_Singh_Rajpoot

C#

using System;
 
// defining the structure for tree nodes
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int v)
    {
        val = v;
        left = null;
        right = null;
    }
}
 
// defining the Solution class to check
// if a binary tree is balanced
public class Solution {
 
    // helper function to determine if a
    // binary tree is balanced
    public(bool, int) IsBalancedfast(Node root)
    {
        // base case: if root is null,
        // the tree is balanced
        // and has height 0
        if (root == null) {
            return (true, 0);
        }
 
        // recursively call IsBalancedfas
        // t function on left & right subtrees
        var left = IsBalancedfast(root.left);
        var right = IsBalancedfast(root.right);
 
        // retrieve whether left and right
        // subtrees are balanced
        bool leftAns = left.Item1;
        bool rightAns = right.Item1;
 
        // check the difference in heights of
        // left and right subtrees
        bool diff = Math.Abs(left.Item2 - right.Item2) <= 1;
 
        // if both subtrees are balanced
        // and their heights differ by at most
        // 1, the tree is balanced
        if (leftAns && rightAns && diff) {
            return (true,
                    Math.Max(left.Item2, right.Item2) + 1);
        }
        // otherwise, the tree is not balanced
        else {
            return (false, 0);
        }
    }
    // Function to check whether a binary
    // tree is balanced or not.
    public bool IsBalanced(Node root)
    {
        return IsBalancedfast(root).Item1;
    }
}
 
// Driver Code
public class Program {
    public static void Main(string[] args)
    {
        // create a binary tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.left.left = new Node(8);
 
        // create an object of Solution class
        Solution obj = new Solution();
 
        // check if the binary tree is
        // balanced using the
        // IsBalanced function
        if (obj.IsBalanced(root)) {
            Console.WriteLine(
                "The given binary tree is balanced.");
        }
        else {
            Console.WriteLine(
                "The given binary tree is not balanced.");
        }
    }
}

Java

// defining the structure for tree nodes
class Node {
    int val;
    Node left, right;
 
    public Node(int v) {
        val = v;
        left = null;
        right = null;
    }
}
 
// defining the Solution class to check if a binary tree is balanced
class Solution {
    // helper function to determine if a binary tree is balanced
    private Pair<Boolean, Integer> isBalancedfast(Node root) {
        // base case: if root is null, the tree is balanced and has height 0
        if (root == null) {
            Pair<Boolean, Integer> p = new Pair<>(true, 0);
            return p;
        }
 
        // recursively call isBalancedfast function on left and right subtrees
        Pair<Boolean, Integer> left = isBalancedfast(root.left);
        Pair<Boolean, Integer> right = isBalancedfast(root.right);
 
        // retrieve whether left and right subtrees are balanced
        boolean leftAns = left.first;
        boolean rightAns = right.first;
 
        // check the difference in heights of left and right subtrees
        boolean diff = Math.abs(left.second - right.second) <= 1;
 
        // create a pair to store the answer (whether the tree is balanced) and its height
        Pair<Boolean, Integer> ans = new Pair<>(false, Math.max(left.second, right.second) + 1);
 
        // if both subtrees are balanced and their heights differ by at most 1, the tree is balanced
        if (leftAns && rightAns && diff) {
            ans = new Pair<>(true, Math.max(left.second, right.second) + 1);
        }
 
        return ans;
    }
 
    // Function to check whether a binary tree is balanced or not.
    public boolean isBalanced(Node root) {
        return isBalancedfast(root).first;
    }
}
 
// Driver Code
public class Main {
    public static void main(String[] args) {
        // create a binary tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.left.left = new Node(8);
 
        // create an object of the Solution class
        Solution obj = new Solution();
 
        // check if the binary tree is balanced using the isBalanced function
        if (obj.isBalanced(root)) {
            System.out.println("The given binary tree is balanced.");
        } else {
            System.out.println("The given binary tree is not balanced.");
        }
    }
}

Python3

# defining the structure for tree nodes
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
# defining the Solution class to check if a binary tree is
# balanced
class Solution:
    # helper function to determine if a binary tree is
    # balanced
    def isBalancedfast(self, root):
        # base case: if root is None, the tree is balanced
        # and has height 0
        if root is None:
            return True, 0
        # recursively call isBalancedfast function on left
        # and right subtrees
        left = self.isBalancedfast(root.left)
        right = self.isBalancedfast(root.right)
 
        # retrieve whether left and right subtrees are
        # balanced
        leftAns = left[0]
        rightAns = right[0]
 
        # check the difference in heights of left and right
        # subtrees
        diff = abs(left[1] - right[1]) <= 1
 
        # set the height of the current node
        height = max(left[1], right[1]) + 1
        # if both subtrees are balanced and their heights
        # differ by at most 1, the tree is balanced
        if leftAns and rightAns and diff:
            return True, height
        # otherwise, the tree is not balanced
        else:
            return False, height
 
    # Function to check whether a binary tree is balanced
    # or not.
    def isBalanced(self, root):
        return self.isBalancedfast(root)[0]
 
# create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(8)
 
# create an object of the Solution class
obj = Solution()
# check if the binary tree is balanced using the
# isBalanced function
if obj.isBalanced(root):
    print("The given binary tree is balanced.")
else:
    print("The given binary tree is not balanced.")

Javascript

// defining the structure for tree nodes
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
 
// defining the Solution class to check if a binary tree is
// balanced
class Solution 
{
 
// helper function to determine if a binary tree is
// balanced
isBalancedfast(root) 
{
 
// base case: if root is null, the tree is balanced
// and has height 0
if (root == null) {
return [true, 0];
}
 
// recursively call isBalancedfast function on left
// and right subtrees
let left = this.isBalancedfast(root.left);
let right = this.isBalancedfast(root.right);
 
    // retrieve whether left and right subtrees are
    // balanced
    let leftAns = left[0];
    let rightAns = right[0];
 
    // check the difference in heights of left and right
    // subtrees
    let diff = Math.abs(left[1] - right[1]) <= 1;
 
    // create an array to store the answer (whether the
    // tree is balanced) and its height
    let ans = [];
     
    // set the height of the current node
    ans[1] = Math.max(left[1], right[1]) + 1;
     
    // if both subtrees are balanced and their heights
    // differ by at most 1, the tree is balanced
    if (leftAns && rightAns && diff) {
        ans[0] = true;
    }
    // otherwise, the tree is not balanced
    else {
        ans[0] = false;
    }
    return ans;
}
 
// Function to check whether a binary tree is balanced
// or not.
isBalanced(root) {
    return this.isBalancedfast(root)[0];
}
}
 
// create a binary tree
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.left.left.left = new Node(8);
 
// create an object of the Solution class
let obj = new Solution();
 
// check if the binary tree is balanced using the
// isBalanced function
if (obj.isBalanced(root)) {
console.log("The given binary tree is balanced.");
}
else {
console.log("The given binary tree is not balanced.");
}

Output

The given binary tree is not balanced.

Time Complexity: O(N) , where N is the number of nodes present in the tree, This is Because every node of the tree is visited only ones.
Auxiliary Space: O(H) , where h is the height of the binary tree.

Asked in: Amazon, Belzabar, Goldman Sachs, InMobi, Intel, Microsoft, Paytm, Synopsys, Walmart, Zillious

Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

How to determine if a binary tree is height-balanced?

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

C++

C#

Java

Python3

Javascript

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

Beyond Context Overload: How Parlant × Milvus Brings Control and Clarity to LLM Agent Behavior

Understanding IVF Vector Index: How It Works and When to Choose It Over HNSW

LEAVE A REPLY Cancel reply

Most Popular

How to Delete Your Gmail (or Google) Account: 2025 Guide by Ana Jovanovic

How to Delete Your Incognito History in 2025 by Tyler Cross

How to Send an Anonymous Email in 2025: A Simple Guide by Ana Jovanovic

OnePlus Watch 3 43mm review: Don’t let the dinky dimensions put you off

EDITOR PICKS

How to Delete Your Gmail (or Google) Account: 2025 Guide by Ana Jovanovic

How to Delete Your Incognito History in 2025 by Tyler Cross

How to Send an Anonymous Email in 2025: A Simple Guide by Ana Jovanovic

POPULAR POSTS

How to Delete Your Gmail (or Google) Account: 2025 Guide by Ana Jovanovic

How to Delete Your Incognito History in 2025 by Tyler Cross

How to Send an Anonymous Email in 2025: A Simple Guide by Ana Jovanovic

POPULAR CATEGORY

ABOUT US

FOLLOW US