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



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

class Node:

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

class Tree:

    def __init__ ( self , node ) :
        self.root_node = node
        self.flag_height_balanced = True

    def CheckIfHeightBalanced ( self ) :
        return self.flag_height_balanced

    def FindHeight ( self, root ) :

        if ( root == None ) :
            return 0;

        ## The below two calls to FindHeight are similary to a post-order tree traversal.
        height_left_subtree  = self.FindHeight ( root.left )
        height_right_subtree  = self.FindHeight ( root.right )

        if ( abs(height_left_subtree - height_right_subtree) > 1 ) :
             self.flag_height_balanced = False

        return ( 1 + max ( height_left_subtree, height_right_subtree ) )

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 ( root )
        t.FindHeight (root)
        if ( t.CheckIfHeightBalanced () ) :
            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;
};

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
class Node {

    int data;

    Node left, right;

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

class Tree {

    Node root_node;
    boolean flag_height_balanced;

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

    boolean CheckIfHeightBalanced () {
        return flag_height_balanced;
    }

    public 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 ( Math.abs(height_left_subtree - height_right_subtree) > 1 ) {
            flag_height_balanced = false;
        }

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

    public boolean CheckIfHeightBalanced ( Node node ) {

        return flag_height_balanced;
    }

    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 node : tree_roots) {

            Tree t = new Tree(node);
            t.FindHeight (node);

            if (t.CheckIfHeightBalanced()) {
                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.