Recursiverly check if a binary tree is height-balanced

Check if a binary tree is height-balanced

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_Tree

Time complexity of checking if a binary tree is height balanced using recursion : 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).


C++14 Check if a binary tree is 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

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