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 ) :
self.left = None
self.right = None
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.
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 ()
if ( t.CheckIfHeightBalanced (root) ) :
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;
};
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.
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
\
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->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) {
if ( CheckIfHeightBalanced (rootnode) ) {
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;
}
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.
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 n : tree_roots) {
if (n.CheckIfHeightBalanced (n)) {
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