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