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, left_node = None, right_node = None):
        self.left = left_node
        self.right = right_node
        self.data = data

class Tree:

    def FindHeight (self, root):
        if (root == None):
            return 0

        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 CheckIfHeightBalanced (self, root):
        self.flag_height_balanced = True
        self.FindHeight(root)
        return self.flag_height_balanced

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, Node * left_node = nullptr, Node * right_node = nullptr) : data(x), left(left_node), right(right_node)
    {}
};

class Tree {

    private:
    bool flag_height_balanced;

    public:
    Tree () {
    }

    inline bool CheckIfHeightBalanced (Node * root) {
        // Initially set the height balanced flag to true.
        flag_height_balanced = true;
        FindHeight(root);
        return flag_height_balanced;
    }

    int FindHeight (Node * node) {
        if (node == NULL)
            return 0;

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

    Tree t;
    for (auto& root : roots) {
        if (t.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;
    }
}

class Tree {

    boolean flag_height_balanced;

    boolean CheckIfHeightBalanced (Node root) {
        flag_height_balanced = true;
        FindHeight(root);
        return flag_height_balanced;
    }

    public int FindHeight (Node node) {

        if (node == null)
            return 0;

        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(height_left_subtree, height_right_subtree));
    }

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

        Tree t = new Tree();
        for (Node n : roots) {
            if (t.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.