CareerCup

double getBalanceFactor(node *root)
{
   double sum = 0;
   getBalFactCore(root,1,&sum);
   return sum;
}

int getBalFactCore(node *root, int level, double *sum)
{
   if (root==null)
      return 0;
   int desc = getBalFactCore(root->left,level+1,sum) + getBalFactCore(root->right,level+1,sum);
   *sum += desc*1.0/level;
   return desc+1;
}

Can somebody please explain the question? What does '(number of all its descendants/level of node);' mean :((

I think balance factor of a binary tree node is equal to the height of the left sub-tree minus the height of the right sub-tree.

The definition given in the question seems to be wrong...

I agree...all i have ever read is that balance factor of a binary tree node is equal to the height of the left sub-tree minus the height of the right sub-tree..and not their sum...

I do not see anything wrong with the question. Just use recurrsion. Parameter sum is a pointer to an integer which is used to store the number of the current node's decendents plus the node itself.

int BF(Node root, int *sum, int depth) {
   if (root==null)
   {   *sum = 0;
       return 0;
   }
   int *sum1, *sum2, bf1, bf2, bf;
   bf1 = BF(root->left, sum1, depth+1);
   bf2 = BF(root->right, sum2, depth+1);
   *sum = *sum1 + *sum2 + 1;
   bf = *sum/depth;
   return bf + bf1 + bf2;
}

guess this should work....
{

[sum,bf] findBF(node* root)
{
if(root==NULL)
return [0,-1];
[sum1,bf1]=findBF(root->left);
[sum2,bf2]=findBF(root->right);
bf = (bf1 + 1) + (bf2 + 1);
sum = sum1 + sum2 + bf;
return [sum,bf];
}

and final "sum" is what we need....

correct me if im wrong or if i had missed any case....
}

int bfact(node *root)
{
if !(root)
return 0;
if(root->left ==NULL && root->right ==NULL)
return 0;
int bfact =0;
if(root->left !=NULL)
bfact = bfact(root->left) +count(root->left);

if(root->right !=NULL)
bfact = bfact(root->right) + count(root->right);

return bfact;
}

int bfact(node *root)
{
if !(root)
return 0;
if(root->left ==NULL && root->right ==NULL)
return 0;
int bfact =0;
if(root->left !=NULL)
bfact = bfact(root->left) +count(root->left);

if(root->right !=NULL)
bfact = bfact(root->right) + count(root->right);

return bfact;
}

Not satisfied with any of the above answer.

Simple logic is find out the number of descendants for left subtree and right subtree seperately and then take the difference.

int numdesc(node * root) //number of descendants
{
	int sum = 0;
	if(root== NULL)
		return 0;
	sum = sum+numdesc(root->left);
	sum = sum+numdesc(root->rght);
	return ++sum;
}

cout <<"Balance Factor of node = " <<(numdesc(root->left) - numdesc(root->rght))<<endl;

Question Statement is confusing.if it is like finding bf of root, then it is quite easy
.find height of both sub trees and then find difference between two...

Right solution would be-
int BF(Node root, int *sum, int depth) {
if (root==null)
{ *sum = 0;
return 0;
}
int *sum1, *sum2, bf1, bf2, bf;
bf1 = BF(root->left, sum1, depth+1);
bf2 = BF(root->right, sum2, depth+1);
*sum = *sum1 + *sum2 ; // I think as

if(root->left)
*sum++;
if(root->left)
*sum++;

bf = *sum/depth;
return bf + bf1 + bf2;

}

// int sum = 0;
// BalanceFactor(&root, 1, &sum);
int BalanceFactor(node* root, int depth, int* sum)
{
	if(root == null)
		return 0;
	
	int l = 0;
	int r = 0;
	int lsum = 0;
	int rsum = 0;
	
	if(root->left != null)
		l = BalanceFactor(root->left, depth+1, &lsum);
	if(root->right != null)
		r = BalanceFactor(root->right, depth+1, &rsum);
	
	int factor = sum\depth;
	sum = sum + lsum + rsum + 1;
	
	return factor;

}

// int sum = 0;
// BalanceFactor(&root, 1, &sum);
int BalanceFactor(node* root, int depth, int* sum)
{
	if(root == null)
		return 0;
	
	int l = 0;
	int r = 0;
	int lsum = 0;
	int rsum = 0;
	
	if(root->left != null)
		l = BalanceFactor(root->left, depth+1, &lsum);
	if(root->right != null)
		r = BalanceFactor(root->right, depth+1, &rsum);
	
	int factor = sum\depth;
	sum = sum + lsum + rsum + 1;
	
	return factor;

}

int get_balance_factor(node* ptr)
{
static int sum=0;
int x;
if(ptr==NULL)
{
return 0;
}
if(ptr->left==NULL and ptr->right==NULL)
{
return 1;
}
x=get_balance_factor(ptr->left)+get_balance_factor(ptr->right);
sum=sum+x;
return x;
}