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, left = None, right = None):
        self.left = left
        self.right = right
        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.
                 11 
                 / \ ----- height 0  
    height 1--- 22       

    """
    node22 = Node(22)
    root_node11 = Node(11, node22, None)

    """ Tree B is height-balanced.
                  1 
                 / \
    height 1----2   3  
                   / \
                  4   5 ----- height 2
    """
    node2 = Node(2)
    node4 = Node(4)
    node5 = Node(5)
    node3 = Node(3, node4, node5)
    root_node1  = Node(1, node2, node3)

    """ Tree C is not height-balanced as height difference is abs(1-3) = 2.
                           10 
                          / \
             height 1--- 20  30  
                            / \
                           70  40
                              / \
                             50  60 ------- height 3
    """

    node20 = Node(20)
    node70 = Node(70)
    node50 = Node(50)
    node60 = Node(60)
    node40 = Node(40, node50, node60)
    node30 = Node(30, node70, node40)
    root_node10 = Node(10, node20, node30)

    roots = [root_node11, root_node1, root_node10]

    t = Tree ()
    for root in roots :
        if (t.CheckIfHeightBalanced(root)) :
            print("Tree with root (" + str(root.data) + ") is height balanced.")
        else :
            print("Tree with root (" + str(root.data) + ") is not height balanced.")

if __name__ == "__main__":
    main()

Output

Tree with root (11) is height balanced.
Tree with root (1) is height balanced.
Tree with root (10) is not height balanced.
#include<iostream>
#include<vector>

using namespace std;

class Node {

    public:
    int data;
    Node * left;
    Node * right;
    Node(int x) : data(x), left(nullptr), right(nullptr)
    {}
    Node(int x, Node* left_node, Node* right_node) : data(x), left(left_node), right(right_node)
    {}
};

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.

                  11 
                 / \ ----- height 0  
    height 1--- 22    
    */

    Node node22(22);
    Node root_node11(11, &node22, nullptr);

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

    Node node4(4), node5(5), node2(2);
    Node node3(3, &node4, &node5);
    Node root_node1(1, &node2, &node3);


    /* Tree C is not height-balanced as height difference is abs(1-3) = 2.
                   10 
                  / \
     height 1--- 20  30  
                      \
                      40
                      / \
                     50  60 ------- height 3
    */
    Node node50(50), node60(60), node20(20);
    Node node40(40, &node50, &node60);
    Node node30(30, nullptr, &node40);
    Node root_node10(10, &node20, &node30);

    vector<Node> roots = { root_node11, root_node1, root_node10 };

    for (auto& root : roots) {

        if ( CheckIfHeightBalanced (&root) ) {
            cout << "Tree with root node (" << root.data << ") is height balanced." << endl;
        } else {
            cout << "Tree with root node (" << root.data << ") is not height balanced." << endl;
        }
    }
    return 0;
}

Output

Tree with root node (11) is height balanced.
Tree with root node (1) is height balanced.
Tree with root node (10) is not height balanced.
class Node {

    int data;
    Node left, right;

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

    Node (int n, Node left_child, Node right_child) {
        data = n;
        left = left_child;
        right = right_child;
    }

    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.
                      11 
                     / \ ----- height 0  
        height 1--- 22    
        */

        Node root_node11 = new Node(11);
        Node node22 = new Node(22);

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

        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node2 = new Node(2, node4, node5);
        Node root_node1 = new Node(1, node2, node3);

        /* Tree C is not height-balanced as height difference is abs(1-3) = 2.
                       10 
                      / \
        height 1 --- 20  30  
                        / \
                       70  40
                          / \
                         50  60 ------- height 3
        */

        Node node50 = new Node(50);
        Node node60 = new Node(60);
        Node node70 = new Node(70);
        Node node20 = new Node(20);
        Node node40 = new Node(40, node50, node60);
        Node node30 = new Node(30, node70, node40);
        Node root_node10 = new Node(10, node20, node30);

        Node [] roots = {root_node11, root_node1, root_node10};

        for (Node n : roots) {
            if (n.CheckIfHeightBalanced (n)) {
                System.out.println("Tree with node (" + n.data + ") is height balanced.");
            } else {
                System.out.println("Tree with node (" + n.data + ") is not height balanced.");
            }
        }
    }
}

Output

Tree with node (11) is height balanced.
Tree with node (1) is height balanced.
Tree with node (10) is not height balanced.



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