Thread: Balanced Tree

Given a Binary Tree, check whether it is balanced or not. A tree is balanced if difference between height of left and right subtree is not more than one.

Code:

#include <iostream>

using namespace std;

struct binTree {
	int data;
	struct binTree* left;
	struct binTree* right;
};

typedef struct binTree* Tree;

Tree insert(Tree T, int x)
{
	if (T == NULL) {
		T = (Tree)malloc(sizeof(struct binTree));
		T->data = x;
		T->left = T->right = NULL;
	} else if (x > T->data) {
		T->right = insert (T->right, x);
	} else if (x < T->data) {
		T->left = insert(T->left, x);
	}
	return T;
}

int height(Tree T)
{
	if (T == NULL)
		return 0;
	else {
		int l = height(T->left);
		int r = height(T->right);

		return (1+ (l>r?l:r));
	}
}

bool isBalanced(Tree T)
{
	if (T == NULL)
		return true;
	else if (abs(height(T->left) - height(T->right)) > 1)
		return false;
	else
		return isBalanced(T->left) && isBalanced(T->right);
}

Please let me know if there is any bug in this code.

why isBalanced is making recursive calls.
height(Tree T) is a recursive function which returns height of the tree.
By calculating height of left and right tree using height(Tree T) and comparing them should also work?