Recursiverly check if a binary tree is height-balanced

In a height-balanced binary tree, the absolute difference of the height of the left sub-tree and the height of the right sub-tree is less than or equal to 1 at every node.

Steps to check if a binary tree is height-balanced are quite straight-forward.

  1. Find the height of the left sub-tree and right sub-tree. As we need to find the height of the left and right sub-tree at every node, we use recursion.
  2. If the absolute difference between the height of the left sub-tree and the right sub-tree is greater than 1, the tree is not height-balanced.

Note : This is not an efficient method to check if a binary tree is height-balanced as we recursively find the height of the left and the right sub-tree of every node.
Thus every node is visited twice; once while finding if its left and right sub-trees are height-balanced and once when it is a child node whose height needs to be found out.

An efficient approach is to use Tree Traversal which has a time complexity of O(N).

Examples of height balanced and height unbalanced trees Height_Balanced_Trees

Time complexity : O ( N 2 ), where N is the number of nodes in the tree. We find the height of left and right sub-trees of every node in O(N) time as it is visited. Since there are ‘N’ nodes the time taken is O ( N * N ).



Program to check if a binary tree is height-balanced.

class Node:

    def __init__( self, data ) : 
        self.left = None
        self.right = None
        self.data = data 

class Tree:

    def FindHeight ( self, node ) : 
       if (node == None):
           return 0
    
       return ( 1 + max ( self.FindHeight (node.left), self.FindHeight (node.right) ) ) 
    
    def CheckIfHeightBalanced ( self, root ) : 

       if ( root == None ) : 
        return True;

       height_left_subtree  = self.FindHeight ( root.left )
       height_right_subtree  = self.FindHeight ( root.right )
    
       if ( abs(height_left_subtree - height_right_subtree) > 1 ) : 
           return False
    
       return (self.CheckIfHeightBalanced (root.left) and self.CheckIfHeightBalanced (root.right))

def main () :

    """ Tree A is height-balanced.
                  1 
                 / \ ----- height 0  
    height 1--- 2       

    """
    root_a = Node (1) 
    root_a.left = Node (2) 
    
    """ Tree B is height-balanced.
                  1 
                 / \
    height 1----2   3  
                   / \
                  4   5 ----- height 2
    """
    root_b  = Node(1)
    root_b.left  = Node(2)
    root_b.right = Node(3)
    root_b.right.left = Node(4)
    root_b.right.right = Node(5)
    
    """ Tree C is not height-balanced as height difference is abs(1-3) = 2.
                           1 
                          / \
             height 1--- 2   3  
                            / \
                           7   4
                              / \
                             5   6 ------- height 3
    """
    root_c  = Node(1)
    root_c.left  = Node(2)
    root_c.right = Node(3)
    root_c.right.left = Node(7)
    root_c.right.right = Node(4)
    root_c.right.right.left = Node(5)
    root_c.right.right.right = Node(6)
    
    tree_roots = [ root_a, root_b, root_c ]
    
    for root in tree_roots :
        t = Tree ()
        if ( t.CheckIfHeightBalanced (root) ) : 
            print ( "Tree is height balanced" )
        else :
            print ( "Tree is not height balanced" )

if __name__ == "__main__":
    main()

Output

Tree is height balanced
Tree is height balanced
Tree is not height balanced
#include<iostream>
#include<vector>
using namespace std;

class Node{

public:

    Node (int n) : data(n), left(NULL), right(NULL){
    }   
    Node * left;
    Node * right;
    int data;
};

int FindHeight (Node * node) {

    if (node == NULL)
        return 0;
   
    return ( 1 + max ( FindHeight(node->left), FindHeight(node->right ) ) );
}

bool CheckIfHeightBalanced (Node * root) {

    if (root == NULL)
        return true;

    int height_left_subtree  = FindHeight (root->left);
    int height_right_subtree = FindHeight (root->right);

    if ( abs(height_left_subtree - height_right_subtree) > 1 ) { 
        return false;
    }   

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

int main() {

    /* Tree A is height-balanced.

                  1 
                 / \ ----- height 0  
    height 1--- 2    
    */

    Node *root_a = new Node(1);
    root_a->left = new Node(2);

    /* Tree B is height-balanced.
                   1 
                  / \
    height 1---- 2   3  
                    / \
                   4   5 ----- height 2
    */ 

    Node *root_b  = new Node(1);
    root_b->left  = new Node(2);
    root_b->right = new Node(3);
    root_b->right->left  = new Node(4);
    root_b->right->right = new Node(5);

    /* Tree C is not height-balanced as height difference is abs(1-3) = 2.
                   1 
                  / \
     height 1--- 2   3  
                      \
                       4
                      / \
                     5   6 ------- height 3
     
    */ 

    Node *root_c  = new Node(1);
    root_c->left  = new Node(2);
    root_c->right = new Node(3);
    root_c->right->right = new Node(4);
    root_c->right->right->left = new Node(5);
    root_c->right->right->right = new Node(6);

    vector<Node*> tree_roots = { root_a, root_b, root_c };

    for (auto & rootnode : tree_roots) {

        if ( CheckIfHeightBalanced (rootnode) ) { 
            cout << "Tree is height balanced" << endl;
        } else {
            cout << "Tree is not height balanced" << endl;
        }
    }   

    // Deallocate the memory
    delete root_a->left;
    delete root_a;

    delete root_b->right->right;
    delete root_b->right->left;
    delete root_b->right;
    delete root_b->left;
    delete root_b;

    delete root_c->right->right->right;
    delete root_c->right->right->left;
    delete root_c->right->right;
    delete root_c->right;
    delete root_c->left;
    delete root_c;

    return 0;
}

Output

Tree is height balanced
Tree is height balanced
Tree is not height balanced
class Node {

    int data;

    Node left, right;

    Node (int n) {
        data = n;
        left = null;
        right = null;
    }

    public int FindHeight ( Node node ) {

        if ( node == null )
            return 0;

        return ( 1 + Math.max ( FindHeight (node.left), FindHeight (node.right) ) );
    }

    public boolean CheckIfHeightBalanced ( Node node ) {

        if ( node == null ) {
            return Boolean.TRUE;
        }

        int height_left_subtree = FindHeight ( node.left );
        int height_right_subtree = FindHeight ( node.right );

        if ( Math.abs ( height_left_subtree - height_right_subtree ) > 1 ) {
            return Boolean.FALSE;
        }

        return ( CheckIfHeightBalanced (node.left) && CheckIfHeightBalanced (node.right) );
    }

    public static void main (String args[]) {

        /* Tree A is height-balanced.
                      1 
                     / \ ----- height 0  
        height 1--- 2    
        */

        Node root_a = new Node(1);
        root_a.left = new Node(2);

        /* Tree B is height-balanced.
                        1 
                       / \
         height 1---- 2   3  
                     / \
                    4   5 ----- height 2
        */

        Node root_b  = new Node(1);
        root_b.left  = new Node(2);
        root_b.right = new Node(3);
        root_b.right.left  = new Node(4);
        root_b.right.right = new Node(5);

        /* Tree C is not height-balanced as height difference is abs(1-3) = 2.
                       1 
                      / \
        height 1 --- 2   3  
                        / \
                       7   4
                          / \
                         5   6 ------- height 3
        */

        Node root_c  = new Node(1);
        root_c.left  = new Node(2);
        root_c.right = new Node(3);
        root_c.right.left = new Node(7);
        root_c.right.right = new Node(4);
        root_c.right.right.left = new Node(5);
        root_c.right.right.right = new Node(6);

        Node [] tree_roots = { root_a, root_b, root_c };

        for ( Node n : tree_roots) {

            if (n.CheckIfHeightBalanced (n)) {
                System.out.println( "Tree is height balanced" );
            } else {
                System.out.println( "Tree is not height balanced" );
            }
        }
    }
}

Output

Tree is height balanced
Tree is height balanced
Tree is not height balanced



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.