Check if a binary tree is height-balanced using tree-traversal

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

In this approach of checking if the binary-tree is height balanced, we traverse the tree like we do in a post-order tree traversal. Once we reach the leaf node, we return its height to the parent. Thus the parent has heights of both the left and right sub-trees and can determine if the trees below are height-balanced.

Note : Parent node returns its own height as [ 1 + maximum (Height of left-subtree, Height right-subtree) ].

Example: Consider the below binary-tree.
Node 5 and Node 6 are the leaf nodes whose parent is Node 4. These leaf nodes return height 1 to the parent Node 4. As both left and right subtree of Node 4 have height 1, the subtree is balanced at node 4.
Similary the difference in the height of left and right subtrees at node 3 is 1.
But for the root node 1, the height of the left subtree is 1 and the height of the right subtree is 3. Thus the absolute difference in the height of the left and right subtree is greater than 1. Thus the tree is not a balanced binary tree.

Height_Balanced_Trees_Using_Traversal

Examples of height balanced and height unbalanced trees Height_Balanced_Trees

Time complexity of checking if a binary tree is height balanced using tree-traversal : O(N), where N is the number of nodes in the tree. Since every node is visited once and at every node we check if the height of the left and right sub-trees are height balanced, the time complexity is O(N).


Java

Java Program to check if a tree is height-balanced using tree-traversal.

Python

Python Program to check if a tree is height-balanced using tree-traversal.

C++ Program to check if a binary tree is height balanced using tree-traversal.

#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;
};

class Tree {

private:

    Node * root_node;
    bool flag_height_balanced;

public:

    Tree (Node* node) {
        root_node = node;
        flag_height_balanced = true;
    }

    inline bool CheckIfHeightBalanced () {
        return flag_height_balanced;
    }

    int FindHeight (Node * node) {

        if (node == NULL)
            return 0;

        // The below two calls to FindHeight are similary to a post-order tree traversal.
        int height_left_subtree  = FindHeight (node->left);
        int height_right_subtree = FindHeight (node->right);

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

        return ( 1 + max (height_left_subtree, height_right_subtree) );
    }
};

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  
                    / \
                   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);

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

    for (auto & rootnode : tree_roots) {
        Tree t(rootnode);
        t.FindHeight (rootnode);
        if ( t.CheckIfHeightBalanced () ) {
            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-2021, Algotree.org.
All rights reserved.