A Height Balanced Tree is tree where for each node this condition is true.

– The difference between heights of left subtree and right subtree for any node is not more than 1.So we can say that a tree T is Height Balanced when

– Left Sub Tree of T is height balanced

– Right Sub Tree of T is height balanced

and for each node this above condition is true :P

So now

– Start from root.

– find height of Left and Right Subtree.

– If difference is <2

contiue

– else break

call same procedure for left and right child of node.

– The difference between heights of left subtree and right subtree for any node is not more than 1.So we can say that a tree T is Height Balanced when

– Left Sub Tree of T is height balanced

– Right Sub Tree of T is height balanced

and for each node this above condition is true :P

So now

**Approach 1)**– Start from root.

– find height of Left and Right Subtree.

– If difference is <2

contiue

– else break

call same procedure for left and right child of node.

**Pseudo Code**isHeightBalanced ( node root) { if (root==null) return 1; lh = height ( root -> left ) rh = height ( root -> right ) if(lh-rh<2 || rh-lh<2) { return 1 && ( isHeightBalanced ( root -> left ) && isHeightBalanced( root -> right ) ) } else return 0; }

as Complexity of above code is O(n2) , { for each node recursively finding height and recursively finding height balacned }

We can think that while calculating height itself why not to find is a node is heightBalanced or not.

This would be topdown approch.

Approach 2)

bool isHeightBalanced(struct node *root, int* height) { int lh = 0, rh = 0; int l = 0, r = 0; if(root == NULL) { *height = 0; return 1; }//basecase l = isBalanced(root->left, &lh); r = isBalanced(root->right,&rh); //call recursively *height = (lh > rh? lh: rh) + 1; if((lh - rh >= 2) || (rh - lh >= 2)) return 0; else return l&&h; }

//See *height is calculated and its reference would be either &lh or &rh

//Hence we calculated height of tree from root and specified lh/rh height for parent.

//so that lh-rh can be calculated easily

Code :

/* program to check if a tree is height-balanced or not */ #include<stdio.h> #include<stdlib.h> #define bool int struct node { int data; struct node* left; struct node* right; }; struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } bool isBalanced(struct node *root, int* height) { int lh = 0, rh = 0; int l = 0, r = 0; if(root == NULL) { *height = 0; return 1; } l = isBalanced(root->left, &lh); r = isBalanced(root->right,&rh); height = (lh > rh? lh: rh) + 1; if((lh - rh >= 2) || (rh - lh >= 2)) return 0; else return l&&r; } int main() { int height = 0; struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->left->left->left = newNode(7); if(isBalanced(root, &height)) printf("Tree is balanced"); else printf("Tree is not balanced"); return 0; }

See Working code at http://ideone.com/QTnTNe