# Recursiverly check if a binary tree is height-balanced

#### Check if a binary tree is height-balanced

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 Time complexity of checking if a binary tree is height balanced using recursion : 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).

C++14 Check if a binary tree is 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
``````