# 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.
- For Node 3, the difference in the height of left and right subtrees is 1.
- For 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, hence is not a balanced binary tree. Examples 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-2022, Algotree.org.