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

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

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

Examples of height balanced and height unbalanced 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).

C++14 Check if a binary tree is height balanced using tree traversal

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

class Tree {

private:

Node * root_node;
bool flag_height_balanced;

public:

Tree (Node* node) {
root_node = node;
flag_height_balanced = true;
}

inline bool CheckIfHeightBalanced () {
return flag_height_balanced;
}

int FindHeight (Node * node) {

if (node == NULL)
return 0;

// The below two calls to FindHeight are similary to a post-order tree traversal.
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.

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

vector<Node*> tree_roots = { root_a, root_b, root_c };

for (auto & rootnode : tree_roots) {
Tree t(rootnode);
t.FindHeight (rootnode);
if ( t.CheckIfHeightBalanced () ) {
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
``````