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

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

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) ].

Examples of height balanced and height unbalanced trees Height_Balanced_Tree

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).


C++14 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-2020, Algotree.org.
All rights reserved.