CareerCup

int banancedBSTHelper(node* root, bool isBalanced)
{
	int leftHight, rightHight;
	if(root==0) return 0;
	leftHight=banancedBSTHelper(root->left, isBalanced)+1;
	rightHight=banancedBSTHelper(root->right, isBalanced)+1;
	if(ABS(leftHight-rightHight)>1)
		isBalanced=false;
	return (leftHight>rightHight)?leftHight:rightHight;
}
bool isBalancedBST(node* root)
{
	bool isBalanced=true;
	balancedBSTHelper(root, &isBalanced);
	return isBalanced;
}

anandtechblog.blogspot.com/2010/12/validate-binary-search-tree-google.html

bool isBalanced = true;
int isTreeBalanced(int level, node* ptr)
{
   if(ptr == null) return level;
   int leftDepth = isTreeBalanced(level+1, ptr->left);
   int rightDepth = isTreeBalanced(level+1, ptr->right);
   if(abs(leftDepth - rightDepth) > 1)
      isBalanced = false;
}

int depthOfBT(node *ptr, int level)
{
   if(ptr) return level - 1;
   else
   {
      return max(depthOfBT(ptr->left, level+1), depthOfBT(ptr->right, level + 1));
   }
}

bool isBalanced(node* ptr)
{
   if(ptr!=NULL && abs((depthOfBT(ptr->right) - depthOfBT(ptr->left))  <= 1))
      return true;
   else 
      return false;
}

PPL please explain your algos rather than coding:

I am suggesting folowing algo.

Traverse a tree in any order & check difference between height of left & right subtree for each non-leaf node if it is -1 0 or 1 for all nodes tree is height balanced.


Now you can see there are too many repetition in top down approach.

try same program with bottom up & keep height of left & right subtree & use them for parent node.

Need clarification please reply

int height(btree *node)
{
if(node == NULL)
	return 0;
return max(height(node->left), height(node->right)) + 1;
}

bool isBalanced(btree *node)
{
if(node == NULL)
	return true;
if(abs(height(node->left)-height(node->right))>1)
	return false;
return isBalanced(node->left) && isBalanced(node->right);
}